Lista dwukierunkowa daje każdemu węzłowi dwa wskaźniki — next i prev — dzięki czemu możesz przechodzić w obu kierunkach i usunąć węzeł w O(1), gdy już masz do niego odwołanie (nie ma potrzeby chodzić od głowy, aby znaleźć poprzednika).
Lista dwukierunkowa daje każdemu węzłowi dwa wskaźniki — next i prev — dzięki czemu możesz przechodzić w obu kierunkach i usunąć węzeł w O(1), gdy już masz do niego odwołanie (nie ma potrzeby chodzić od głowy, aby znaleźć poprzednika).
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
Na liście jednokierunkowej usunięcie węzła wymaga najpierw znalezienia jego poprzednika → O(n).
| Aspekt | Jednokierunkowa | Dwukierunkowa |
|---|---|---|
| Wskaźniki na węzeł | 1 (next) | 2 (next, prev) |
| Przechodzenie wstecz | nie | tak |
| Usunięcie znanego węzła | O(n) | O(1) |
| Narzut pamięci | niższy | wyższy |
O(1) splice-out znanego węzła to kluczowa właściwość, która czyni listy dwukierunkowe partnerem map haszujących w cache LRU.
Dodatkowy wskaźnik prev handluje pamięcią za elastyczność ruchu dwukierunkowego i usunięcia w stałym czasie.