Tugann liosta nasc dúbailte dhá phointéir do gach nód — next agus prev — ionas gur féidir leat dul i dhá threo agus nód a scriosadh in O(1) nuair atá tagairt agat dó cheana féin (ní gá siúl ó bharr an chinn chun an réamhtheachtaithe a aimsiú).
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
I liosta nasc aonair, bíonn sé de dhíth an réamhtheachtaithe a aimsiú ar dtús chun nód a scriosadh → O(n).
| Gné | Aonair | Dúbailte |
|---|---|---|
| Pointéirí in aghaidh an nóid | 1 (next) | 2 (next, prev) |
| Dul siar ar an taisteal | ní | is ea |
| Nód ar a bhfuil a fhios agat a scriosadh | O(n) | O(1) |
| Broslucht cuimhne | níos ísle | níos airde |
Is é an faillí O(1) de nód ar a bhfuil a fhios agat an príomhphobal a dhéanann liostaí nasc dúbailte a bheith ina gcomhpháirtí d'imreasc i taisce LRU.
Tradaíonn an pointéir breise prev cuimhne ar son solúbthacht gluaiseachta déathaobhach agus scriostha de dhroim-ordú.
Leabharlann de cheisteanna agallaimh TF le freagraí mionsonraithe — ó Shóisearach go Sinsearach.
Síntiús