Bir çift yönlü bağlı liste, her düğüme iki işaretçi verir — next ve prev — böylece her iki yönde de traverse edebilir ve zaten bir referansınız olduğunda O(1)'de bir düğümü silebilirsiniz (öncü bulabilmek için baştan yürümeye gerek yoktur).
Bir çift yönlü bağlı liste, her düğüme iki işaretçi verir — next ve prev — böylece her iki yönde de traverse edebilir ve zaten bir referansınız olduğunda O(1)'de bir düğümü silebilirsiniz (öncü bulabilmek için baştan yürümeye gerek yoktur).
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
Tek yönlü bir bağlı listede, bir düğümü silmek öncelikle öncülünü bulmayı gerektirir → O(n).
| Yön | Tek yönlü | Çift yönlü |
|---|---|---|
| Düğüm başına işaretçiler | 1 (next) | 2 (next, prev) |
| Geriye doğru traverse | hayır | evet |
| Bilinen düğümü sil | O(n) | O(1) |
| Bellek yükü | daha düşük | daha yüksek |
Bilinen bir düğümün O(1) çıkarılması, çift yönlü bağlı listeleri hash haritaların ortağı yapan LRU cache'de anahtar özelliktir.
Ek prev işaretçisi, belleği çift yönlü harekette esneklik ve sabit zamanda silme karşılığında takas eder.