A kétirányított láncolt lista mindegyik csomópontnak két mutatót ad — next és prev — így mindkét irányban atraversálható és O(1) időben törölhető egy csomópont, ha már van rá hivatkozása (nem kell a fejétől a megelőző csomópontig járni).
A kétirányított láncolt lista mindegyik csomópontnak két mutatót ad — next és prev — így mindkét irányban atraversálható és O(1) időben törölhető egy csomópont, ha már van rá hivatkozása (nem kell a fejétől a megelőző csomópontig járni).
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
Az egyirányított láncolt listában egy csomópont törlése előbb megköveteli az elődjének megtalálását → O(n).
| Szempont | Egyirányított | Kétirányított |
|---|---|---|
| Mutatók csomópontonként | 1 (next) | 2 (next, prev) |
| Visszafelé traversálás | nem | igen |
| Ismert csomópont törlése | O(n) | O(1) |
| Memória terhelés | alacsonyabb | magasabb |
Az O(1) idejű csomópont kivágása az a kulcstulajdonság, amely a kétirányított láncolt listákat az LRU cache hash-térkép partnerévé teszi.
A további prev mutató memóriát cserél az kétirányú mozgás és az állandó idejű törlés rugalmasságáért.
IT interjúkérdések gyűjteménye részletes válaszokkal — Juniortól Seniorig.
Adományozás