Dvakratno povezana lista daje vsakemu vozlišču dve kazalca — next in prev — tako da lahko potujete v obe smeri in izbrišete vozlišče v O(1), ko že imate referenco nanj (ni potrebno hoditi od glave, da najdete predhodnika).
Struktura
text
Dvakratno povezana lista daje vsakemu vozlišču dve kazalca — next in prev — tako da lahko potujete v obe smeri in izbrišete vozlišče v O(1), ko že imate referenco nanj (ni potrebno hoditi od glave, da najdete predhodnika).
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
V enostavno povezani listi zahteva brisanje vozlišča prvo iskanje njegovega predhodnika → O(n).
| Vidik | Enostavna | Dvakratna |
|---|---|---|
| Kazalci na vozlišče | 1 (next) | 2 (next, prev) |
| Potovanje nazaj | ne | da |
| Brisanje znanega vozlišča | O(n) | O(1) |
| Reža pomnilnika | nižja | višja |
O(1) izstranjevanje znanega vozlišča je ključna lastnost, ki naredi dvakratno povezane liste partnerja hash tabel v LRU predpomnilniku.
Dodaten prev kazalec zamenja pomnilnik za fleksibilnost dvosmernega gibanja in brisanja v stalnem času.