Eine doppelt verkettete Liste gibt jedem Knoten zwei Zeiger — next und prev — sodass Sie in beide Richtungen traversieren können und einen Knoten in O(1) löschen können, wenn Sie bereits eine Referenz zu ihm haben (kein Durchlaufen von vorne nötig, um den Vorgänger zu finden).
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
Bei einer einfach verketteten Liste erfordert das Löschen eines Knotens, zuerst seinen Vorgänger zu finden → O(n).
| Aspekt | Einfach | Doppelt |
|---|---|---|
| Zeiger pro Knoten | 1 (next) | 2 (next, prev) |
| Rückwärts traversieren | nein | ja |
| Bekannten Knoten löschen | O(n) | O(1) |
| Speicher-Overhead | niedriger | höher |
Die O(1)-Spleiß-Entfernung eines bekannten Knotens ist die Schlüsseleigenschaft, die doppelt verkettete Listen zum Partner von Hash Maps in einem LRU-Cache macht.
Der zusätzliche prev-Zeiger tauscht Speicher gegen die Flexibilität der bidirektionalen Bewegung und konstante Löschzeit.