Dvikryptė susieta sąrašas kiekvienam mazgui suteikia du rodykles — next ir prev — todėl galite judėti abiem kryptimis ir ištrinti mazgą per O(1), kai jau turite jį žinomo atskaitos (nereikia eiti nuo galvos, kad rastumėte pirmtaką).
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
Vienakrypčiame susietame sąraše mazgo ištrynimas reikalauja pirmiausia rasti jo pirmtaką → O(n).
| Aspektas | Vienakryptė | Dvikryptė |
|---|---|---|
| Rodyklės per mazgą | 1 (next) | 2 (next, prev) |
| Judėti atgal | ne | taip |
| Ištrinti žinomą mazgą | O(n) | O(1) |
| Atminties pridėtinis krūvis | mažesnis | didesnis |
O(1) iš žinomo mazgo yra pagrindinė savybė, kuri daro dvikryptes susietus sąrašus LRU talpyklos hash žemėlapio partneriu.
Papildoma prev rodyklė mainai atmintis dėl dvikriapio judėjimo lankstumo ir pastovios trynimo trukmės.
IT pokalbių klausimų biblioteka su išsamiais atsakymais — nuo Junior iki Senior.
Paaukoti