Μια διπλή συνδεδεμένη λίστα δίνει σε κάθε κόμβο δύο δείκτες — next και prev — ώστε να μπορείτε να διασχίσετε και προς τις δύο κατευθύνσεις και να διαγράψετε έναν κόμβο σε O(1) όταν έχετε ήδη μια αναφορά σε αυτόν (δεν χρειάζεται να περπατήσετε από την αρχή για να βρείτε τον προκάτοχο).
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
Σε μια απλή συνδεδεμένη λίστα, η διαγραφή ενός κόμβου απαιτεί να βρείτε πρώτα τον προκάτοχό του → O(n).
| Πτυχή | Απλή | Διπλή |
|---|---|---|
| Δείκτες ανά κόμβο | 1 (next) | 2 (next, prev) |
| Διάσχιση προς τα πίσω | όχι | ναι |
| Διαγραφή γνωστού κόμβου | O(n) | O(1) |
| Επιβάρυνση μνήμης | χαμηλότερη | υψηλότερη |
Η διαγραφή O(1) ενός γνωστού κόμβου είναι η βασική ιδιότητα που κάνει τις διπλές συνδεδεμένες λίστες εταίρο των χαρτών κατακερματισμού σε έναν LRU cache.
Ο επιπλέον δείκτης prev ανταλλάσσει μνήμη για την ευελιξία της δίδρομης κίνησης και της διαγραφής σε σταθερό χρόνο.