Një listë e lidhur dyfishi i jep secilit nyje dy tregues — next dhe prev — në mënyrë që të mund të kaloni në të dy drejtimet dhe të fshini një nyje në O(1) kur tashmë keni një referencë për të (nuk ka nevojë të ecni nga koka për të gjetur paraardhësin).
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
Në një listë njeri të lidhur, fshirja e një nyje kërkon gjetjen e paraardhësit të saj treguese → O(n).
| Aspekti | Njeri | Dyfishi |
|---|---|---|
| Tregues për nyje | 1 (next) | 2 (next, prev) |
| Kalimi prapa | jo | po |
| Fshirja e nyjes të njohur | O(n) | O(1) |
| Sipërtharja e kujtesës | më e ulët | më e lartë |
O(1) heqja e njohur e një nyje të njohur është pronësia kyçe që bën listërat e lidhura dyfishe bashkëpunëtore të hartave hash në një memorje LRU.
Treguesit shtesë prev ndërron kujtesën për fleksibilitetin e lëvizjes dypalëshe dhe fshirjes në kohë konstante.