Dvoupropojený seznam dává každému uzlu dva ukazatele — next a prev — takže můžete procházet oběma směry a odstranit uzel v O(1), když již máte referenci na něj (není potřeba procházet z hlavy, abyste našli předchůdce).
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
V jedenpropojovaném seznamu vyžaduje odstranění uzlu nejprve nalezení jeho předchůdce → O(n).
| Aspekt | Jedenpropojovaný | Dvoupropojovaný |
|---|---|---|
| Ukazatele na uzel | 1 (next) | 2 (next, prev) |
| Procházení dozadu | ne | ano |
| Odstranění známého uzlu | O(n) | O(1) |
| Režie paměti | nižší | vyšší |
O(1) vytlačení známého uzlu je klíčová vlastnost, která činí dvoupropojované seznamy partnerem hash map v mezipaměti LRU.
Dodatný ukazatel prev obchoduje paměť za flexibilitu obousměrného pohybu a odstranění v konstantním čase.