Care este complexitatea asimptotică a operațiilor cu elemente în listă?

Depinde de tipul de listă și de operație.

De obicei, se consideră următoarele tipuri de liste:

• Listă simplu înlănțuită
• Listă dublu înlănțuită
• Array (ca un caz particular de listă)

Operații:

• Acces după index
• Inserare
• Ștergere
• Căutare valoare

Operație	Listă simplu înlănțuită	Listă dublu înlănțuită	Array
Acces după index	O(n)	O(n)	O(1)
Inserare	O(1) (la început)	O(1) (la început/la sfârșit)	O(n)
Ștergere	O(n)	O(n)	O(n)
Căutare valoare	O(n)	O(n)	O(n)

Explicații:

• O(1) (Timp constant): Operația durează un timp fix, indiferent de dimensiunea listei. De exemplu, accesul la un element după index într-un array.
• O(n) (Timp liniar): Timpul de execuție al operației este proporțional cu dimensiunea listei. De exemplu, căutarea unui element într-o listă nesortată.
• O(log n) (Timp logaritmic): Timpul de execuție crește logaritmic cu dimensiunea listei. Se întâlnește frecvent în lucrul cu date sortate (de exemplu, căutare binară).

Detalii:

• Într-o listă simplu înlănțuită: Inserare la început - O(1). Inserare la sfârșit sau inserare/ștergere după index necesită parcurgerea listei până la elementul dorit, ceea ce dă O(n).
• Într-o listă dublu înlănțuită: Inserare la început și sfârșit - O(1). Inserare/ștergere la o poziție dată - O(1), dar căutarea acestui nod după valoare sau index - O(n).
• Într-un array: Acces după index - O(1). Inserarea sau ștergerea în mijlocul array-ului necesită deplasarea elementelor, ceea ce dă O(n). Inserare/ștergere la sfârșit, dacă există capacitate rezervată (de exemplu, în std::vector cu o anumită capacitate), poate fi O(1) în medie, dar în cel mai rău caz (reallocare) O(n).