Cum se evaluează complexitatea temporală a operațiilor de inserare, ștergere și căutare a elementelor într-o listă legată?

Complexitatea temporară a operațiilor într-o listă legată depinde de ceea ce facem exact și dacă avem acces la elementul necesar:

• Inserare:

  • La începutul listei — O(1), deoarece este suficient să schimbăm legăturile.
  • La sfârșitul unei liste simplu legate fără pointer către coadă — O(n), trebuie să parcurgem întreaga listă.
  • La sfârșit cu un pointer către coadă — O(1).
  • Într-un loc arbitrar (după index sau valoare) — O(n), deoarece trebuie să găsim poziția.

• Ștergere:

  • Ștergerea primului element — O(1).
  • Ștergerea după valoare sau index — O(n), deoarece trebuie să găsim elementul și predecesorul său.

• Căutare:

  • Căutarea unui element după valoare — O(n), deoarece trebuie să parcurgem lista.

Prin urmare, operațiile principale necesită timp liniar dacă nu există acces direct la nodul necesar. Acest lucru se datorează naturii secvențiale a listelor legate.