Care este estimarea complexității temporale a operației de ștergere a unui element dintr-o listă simplu înlănțuită?

Complexitatea temporară a eliminării unui element dintr-o listă simplu înlănțuită depinde de faptul dacă avem un pointer către elementul de eliminat sau doar către capul listei.

• Dacă trebuie să eliminăm un element, cunoscând doar capul listei, trebuie mai întâi să parcurgem lista pentru a găsi elementul și nodul său anterior. Acest lucru durează O(n) timp, unde n este numărul de elemente din listă.
• Dacă avem un pointer către elementul anterior (sau către elementul de eliminat, dacă este primul), eliminarea se face în O(1), deoarece trebuie doar să reconfigurăm legăturile.

Prin urmare, în general, eliminarea unui element dintr-o listă simplu înlănțuită este o operație cu complexitate temporară O(n).