En dubbeltlänkad lista ger varje nod två pekare — next och prev — så att du kan traversera i båda riktningarna och ta bort en nod i O(1) när du redan har en referens till den (inget behov av att gå från huvudet för att hitta föregångaren).
En dubbeltlänkad lista ger varje nod två pekare — next och prev — så att du kan traversera i båda riktningarna och ta bort en nod i O(1) när du redan har en referens till den (inget behov av att gå från huvudet för att hitta föregångaren).
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
I en enkeltlänkad lista kräver borttagning av en nod att man först hittar dess föregångare → O(n).
| Aspekt | Enkeltlänkad | Dubbeltlänkad |
|---|---|---|
| Pekare per nod | 1 (next) | 2 (next, prev) |
| Traversera bakåt | nej | ja |
| Ta bort känd nod | O(n) | O(1) |
| Minnesöverhead | lägre | högre |
O(1) utsprickningen av en känd nod är den nyckelskap som gör dubbeltlänkade listor till partnern till hash-kartor i en LRU-cache.
Den extra prev pekaren byter minne för flexibiliteten av dubbelriktad rörelse och konstant-tid borttagning.