En doubly linked list gir hver node to pekere — next og prev — slik at du kan traversere i begge retninger og slette en node i O(1) når du allerede har en referanse til den (ingen grunn til å gå fra hodet for å finne forgjengeren).
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 singly linked list krever sletting av en node at du først finner forgjengeren → O(n).
| Aspekt | Singly | Doubly |
|---|---|---|
| Pekere per node | 1 (next) | 2 (next, prev) |
| Traversere bakover | nei | ja |
| Slette kjent node | O(n) | O(1) |
| Minne overhead | lavere | høyere |
O(1) splice-out av en kjent node er nøkkeegenskapen som gjør doubly linked lists til partner av hash maps i en LRU cache.
Den ekstra prev pekeren bytter minne for fleksibiliteten av toveis bevegelse og sletting i konstant tid.