एक doubly linked list प्रत्येक node को दो pointers देती है — next और prev — ताकि आप दोनों दिशाओं में traverse कर सकें और जब आपके पास पहले से किसी node का reference हो तो उसे O(1) में delete कर सकें (पूर्ववर्ती को खोजने के लिए head से चलने की आवश्यकता नहीं)।
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
एक singly linked list में, किसी node को delete करने के लिए पहले उसके पूर्ववर्ती को खोजना पड़ता है → O(n)।
| Aspect | Singly | Doubly |
|---|---|---|
| Pointers per node | 1 (next) | 2 (next, prev) |
| Traverse backward | no | yes |
| Delete known node | O(n) | O(1) |
| Memory overhead | lower | higher |
किसी ज्ञात node का O(1) splice-out वह मुख्य गुण है जो doubly linked lists को LRU cache में hash maps का साथी बनाता है।
अतिरिक्त prev pointer द्विदिशात्मक गति और स्थिर-समय deletion की लचीलापन के बदले memory का व्यापार करता है।