Cum se determină complexitatea temporală a eliminării unui element situat în mijlocul unei liste legate?

Complexitatea temporară a eliminării unui element din mijlocul unei liste legate depinde de dacă aveți acces direct la acel element și la nodul său anterior.

• Dacă aveți un pointer către elementul în sine și către nodul anterior (de exemplu, într-o listă dublu legată), eliminarea se face în O(1), deoarece trebuie doar să reconfigurați legăturile.
• Dacă aveți doar valoarea sau un pointer către element fără acces la anterior, mai întâi trebuie să parcurgeți lista de la început până la acel element, ceea ce durează O(n), unde n este numărul de elemente înainte de cel de eliminat.

Prin urmare, în general, eliminarea din mijlocul unei liste legate este considerată o operație cu complexitatea temporală O(n), dacă nu aveți acces direct la nodul anterior.