Orodha iliyounganishwa kabla inatoa kila nodi viashiria viwili — next na prev — ili uweze kutembea kwa njia zote mbili na kuondoa nodi katika O(1) wakati umeshakuwa na kumbuke yake (hakuna haja ya kutembea kutoka kwa kichwa kupata ambaye anakuja kabla).
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
Katika orodha iliyounganishwa moja kwa moja, kuondoa nodi kunahitaji kutafuta ambaye anakuja kabla kwanza → O(n).
| Sehemu | Moja kwa moja | Kabla |
|---|---|---|
| Viashiria kwa kila nodi | 1 (next) | 2 (next, prev) |
| Kutembea nyuma | hapana | ndiyo |
| Kuondoa nodi inayojulikana | O(n) | O(1) |
| Ziada ya kumbukumbu | kuingilia | juu zaidi |
O(1) kuondolewa kwa nodi inayojulikana ni sifa ya muhimu inayofanya orodha iliyounganishwa kabla kuwa rafiki wa ramani za hash katika kumbukumbu ya LRU.
Viashiria vya ziada vya prev vinabadilisha kumbukumbu kwa njia rahisi ya mwendo wa njia zote mbili na kuondolewa kwa wakati kamili.