Dvostruko povezana lista daje svakom čvoru dva pokazivača — next i prev — što vam omogućava prelazak u oba smjera i brisanje čvora u O(1) kada već imate referencu na njega (nije potrebno hodati od početka kako biste pronašli prethodnika).
Dvostruko povezana lista daje svakom čvoru dva pokazivača — next i prev — što vam omogućava prelazak u oba smjera i brisanje čvora u O(1) kada već imate referencu na njega (nije potrebno hodati od početka kako biste pronašli prethodnika).
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
U jednostruko povezanoj listi, brisanje čvora zahtijeva pronalaženje njegovog prethodnika prvo → O(n).
| Aspekt | Jednostruko | Dvostruko |
|---|---|---|
| Pokazivači po čvoru | 1 (next) | 2 (next, prev) |
| Prelazak unazad | ne | da |
| Brisanje poznatog čvora | O(n) | O(1) |
| Memorijska potrošnja | niža | viša |
O(1) uklanjanje poznatog čvora je ključno svojstvo koje čini dvostruko povezane liste partnerom hash mapi u LRU cacheu.
Dodatni prev pokazivač traži memoriju za fleksibilnost dvosmjerne kretnje i brisanja u konstantnom vremenu.
Knjižnica IT pitanja za razgovore za posao s detaljnim odgovorima — od Juniora do Seniora.
Doniraj