Care este complexitatea temporală a operației de adăugare a unui element la sfârșitul unei liste dublu înlănțuite?

Complexitatea temporară de adăugare a unui element la sfârșitul unei liste dublu înlănțuite depinde de existența sau nu a unui pointer către ultimul element (coadă).

• Dacă există un pointer către coadă, adăugarea elementului la sfârșit se face în O(1), deoarece se poate accesa direct ultimul element și se adaugă noul după el.

• Dacă nu există un pointer către coadă, trebuie parcursă întreaga listă de la cap până la ultimul element, ceea ce durează O(n) timp, unde n este numărul de elemente din listă.

În majoritatea implementărilor de liste dublu înlănțuite, pentru a optimiza operațiile de adăugare la sfârșit, se păstrează un pointer către coadă, astfel încât operația este de obicei considerată O(1).