Een doubly linked list geeft elk knooppunt twee aanwijzers — next en prev — zodat u in beide richtingen kunt doorlopen en een knooppunt in O(1) kunt verwijderen wanneer u al een verwijzing ernaar hebt (geen noodzaak om vanaf het begin naar de voorganger te zoeken).
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
In een singly linked list vereist het verwijderen van een knooppunt dat u eerst zijn voorganger vindt → O(n).
| Aspect | Singly | Doubly |
|---|---|---|
| Aanwijzers per knooppunt | 1 (next) | 2 (next, prev) |
| Achterwaarts doorlopen | nee | ja |
| Bekend knooppunt verwijderen | O(n) | O(1) |
| Geheugen overhead | lager | hoger |
De O(1) splice-out van een bekend knooppunt is de sleuteleigenschap die doubly linked lists tot partner van hash maps in een LRU cache maakt.
De extra prev aanwijzer verruilt geheugen voor de flexibiliteit van bidirectioneel verkeer en verwijdering in constante tijd.
De O(1) splice-out van een bekend knooppunt is de sleuteleigenschap die doubly linked lists tot partner van hash maps in een LRU cache maakt.
De extra prev aanwijzer verruilt geheugen voor de flexibiliteit van bidirectioneel verkeer en verwijdering in constante tijd.