O listă dublu legată oferă fiecărui nod doi pointeri — next și prev — deci puteți traversa în ambele direcții și puteți șterge un nod în O(1) când deja aveți o referință la acesta (nu este necesar să mergeți de la cap pentru a găsi predecesorul).
null <- [10] <-> [20] <-> [30] -> null
prev/next links in BOTH directions
class Node:
def __init__(self, val):
self.val, self.prev, self.next = val, None, None
def remove(node): # O(1) — no traversal needed
if node.prev: node.prev.next = node.next
if node.next: node.next.prev = node.prev
Într-o listă simplu legată, ștergerea unui nod necesită mai întâi găsirea predecesorului acestuia → O(n).
| Aspect | Simplu legată | Dublu legată |
|---|---|---|
| Pointeri per nod | 1 (next) | 2 (next, prev) |
| Traversare înapoi | nu | da |
| Ștergere nod cunoscut | O(n) | O(1) |
| Overhead de memorie | mai mic | mai mare |
Splicerea O(1) a unui nod cunoscut este proprietatea-cheie care face listele dublu legate partenere ale tabelelor hash într-un cache LRU.
Pointerul suplimentar prev schimbă memoria pentru flexibilitatea mișcării bidirecționale și ștergerea în timp constant.