Înțelegerea complexității timpului operațiunilor legate de liste este esențială pentru evaluarea eficienței acestora. Acest articol oferă o analiză clară, graduală, a operațiunilor comune legate de liste și a costurilor lor de calcul.

Operaţiuni de bază şi complexităţile lor

Operaţiunile de listă conectată includ inserţia, ştergerea şi traversarea. Complexitatea timpului fiecărei operaţiuni depinde de faptul dacă lista este conectată individual sau dublu şi dacă poziţia operaţiunii este cunoscută.

Operațiuni de inserție

Introducerea unui nod la începutul unei liste legate necesită timp constant, O(1), deoarece implică actualizarea câtorva puncte. Cu toate acestea, introducerea într-o anumită poziție necesită traversarea listei către acea poziție, care are nevoie de timp liniar, ]O(n).

Operațiuni de eliminare

Eliminarea primului nod este o operațiune O(1), deoarece implică doar actualizări ale pointerului. Eliminarea unui nod la o anumită poziție necesită traversare către acel nod, rezultând o complexitate ]O [n].

Traversare și căutare

Traversarea unei liste legate pentru a găsi un element specific sau pentru a ajunge la final implică vizitarea fiecărui nod o dată, ceea ce duce la o complexitate liniară a timpului de O [n]].

  • Se introduce în cap: O(1)
  • Se introduce la poziție: O(n)
  • Deleția la cap: O(1)
  • Deleția în poziție: O(n)
  • Traversare/căutare: O(n)