Doubly linked list — bidirectional traversal

3.2.3 · Coding › Linear Data Structures

Doubly Linked List Kya Hai?

   head                              tail
    │                                 │
    ▼                                 ▼
  ┌────┬───┬────┐   ┌────┬───┬────┐  ┌────┬───┬────┐
  │null│ A │  ──┼──▶│ ◀──┤ B │  ──┼─▶│ ◀──┤ C │null│
  └────┴───┴────┘◀──┴────┴───┴────┘◀─┴────┴───┴────┘
   prev data next   prev data next   prev data next

Ek zaroori invariant (ek rule jo hamesha hold karna chahiye):

$for every node x : x . n e x t . p r e v = x and x . p r e v . n e x t = x$

(jab bhi wo neighbours exist karte hain). Agar tum ise kabhi tod dete ho, toh traversal tumhe galat result dega.

Figure — Doubly linked list — bidirectional traversal

Bidirectional Traversal — Scratch Se Derive Karna

KYA chahiye: har node ko ya toh left-to-right ya right-to-left visit karna.

KAISE, forward (head → tail):

def traverse_forward(head):
    cur = head
    while cur is not None:      # stop when we fall off the end
        visit(cur.data)
        cur = cur.next          # step one door forward

cur is not None kyun? Kyunki aakhri node ka next null hai. None tak pahunchna hi signal hai "aur koi node nahi."

KAISE, backward (tail → head):

def traverse_backward(tail):
    cur = tail
    while cur is not None:
        visit(cur.data)
        cur = cur.prev          # step one door backward

tail se shuru kyun karte hain, head se nahi? Kyunki peeche jaane ka matlab hai prev ko follow karna. Shuru karne ke liye humein peeche koi node chahiye. tail store karne ka yahi faida hai: backward traversal shuru se $O (n)$ hai, kabhi $O (n^{2})$ nahi.

Worked Example 1 — Pehle Forward Phir Backward Print Karo

List: 10 ⇄ 20 ⇄ 30. head → node(10), tail → node(30).

Forward:

step	`cur`	action	next `cur`
1	10	print 10	`cur=cur.next` → 20
2	20	print 20	→ 30
3	30	print 30	→ `None`
4	None	loop ends	—

Output: 10 20 30. Step 4 kyun? 30.next None hai, isliye while condition fail ho jaati hai — ye ek clean stop hai, koi off-by-one error nahi.

Backward (tail=30 se shuru): Output: 30 20 10, har baar prev follow karke. Ye kyun kaam karta hai: invariant guarantee karta hai 30.prev = 20, 20.prev = 10, 10.prev = None.

Worked Example 2 — Middle Mein Insert Karo (aur Invariant Rakho)

20 aur 30 ke beech 25 insert karo.

def insert_after(node, new):
    new.prev = node            # 1
    new.next = node.next       # 2
    if node.next is not None:  # 3
        node.next.prev = new   # 4
    else:
        tail = new             # 4'  (node was the tail)
    node.next = new            # 5

Ye exact order kyun? Steps 1–2 new ko uske neighbours se wire karte hain pehle, jab purane links abhi exist karte hain. Agar tum step 5 (node.next = new) jaldi kar dete, tum 30 ka pointer kho dete aur uska prev fix karne ke liye usse reach nahi kar sakte. New node ko attach karo purane links hatane se pehle.

Insert ke baad, invariant check karo: 25.next.prev = 30.prev = 25 ✓ aur 25.prev.next = 20.next = 25 ✓. Bidirectional traversal ab sahi se 10 20 25 30 forward aur ulta backward produce karta hai.

Worked Example 3 — Tail Pointer Ke Bina Reverse Traversal

Kya ho agar sirf head hai? Tum phir bhi peeche ja sakte ho — lekin pehle aage end tak walk karna padega:

cur = head
while cur.next is not None:    # walk to last node: O(n)
    cur = cur.next
while cur is not None:         # now walk back: O(n)
    visit(cur.data)
    cur = cur.prev

Ye abhi bhi theek kyun hai? Total $O (n) + O (n) = O (n)$ . tail store karna sirf pehli walk bachata hai. prev pointers kisi bhi case mein asli kaam karte hain.

Common mistake Classic Errors Ko Steel-man Karna

Galti A: "Ek doubly linked list mujhe $O (lo g n)$ mein ya instantly backward traverse karne deta hai." Ye sahi kyun lagta hai: prev hona powerful lagta hai, jaise random access. Fix: prev sirf ek step peeche $O (1)$ mein deta hai. Saare nodes ko backward visit karna abhi bhi $O (n)$ hai — tum poori chain chalte ho.

Galti B: Insert/Delete par sirf ek pointer update karna. Ye sahi kyun lagta hai: singly list mein tum sirf next ko touch karte the, isliye muscle memory ek side update karti hai. Fix: har structural change har affected boundary par do links touch karta hai (prev aur next). Har edit ke baad invariant $x . n e x t . p r e v = x$ dobara check karo.

Galti C: while cur.next is not None se loop karna jab tum aakhri node bhi visit karna chahte the. Ye sahi kyun lagta hai: ye padhne mein lagta hai "jab tak next hai." Fix: wo condition aakhri node skip kar deti hai. Saare nodes visit karne ke liye while cur is not None use karo; while cur.next is not None tabhi use karo jab tum jaan-bujhkar aakhri node par rokna chahte ho (jaise tail dhundhne ke liye).

Recall Feynman: ek 12-saal ke bacche ko explain karo

Socho ek line mein khade bachche haath pakde hue hain. Normal (singly) line mein, har baccha sirf aage wale bacche ka haath pakdta hai. Agar tum peeche jaana chahte ho, toh dobara shuru se chalna padega. Doubly linked line mein, har baccha dono taraf haath pakdta hai — aage bhi aur peeche bhi. Isliye tum aage end tak chal sakte ho, phir bas palto aur peeche wale haath follow karte hue shuru tak aa jao. Agar beech mein koi naya baccha aata hai, toh uske dono taraf ke bachche ko naye bacche ka haath pakdna hoga — dono taraf se — warna chain toot jaayegi aur koi kho jaayega.

Active Recall

Ek doubly linked list, singly linked list ke upar kaunsa extra pointer add karta hai?

Har node mein ek prev pointer, jo pichle node ki taraf point karta hai.

Head node ka prev aur tail node ka next kya hota hai?

Dono null (None) hote hain.

DLL mein saare nodes backward traverse karne ki time complexity?

O(n) — tum abhi bhi har node ko ek baar visit karte ho.

DLL mein exactly ek node peeche step karne ki time complexity vs. singly linked list?

DLL mein O(1); singly list mein O(n) (head se restart karna padta hai).

Doubly linked list ka invariant batao.

Har node x ke liye: x.next.prev x aur x.prev.next x (jab neighbours exist karein).

tail pointer kyun store karte hain?

Taaki backward traversal turant end se shuru ho sake, pehle ek O(n) forward walk se bachke.

insert_after mein, node.next rewrite karne se pehle naye node ke links attach kyun karte hain?

Kyunki pehle node.next rewrite karne se purane successor ka pointer kho jaata, aur uska prev fix karne ke liye wo reachable nahi rehta.

Kaun si loop condition SAARE nodes visit karti hai, including aakhri wala?

while cur is not None (na ki while cur.next is not None).

Singly list ke upar DLL ki extra space cost?

O(n) — har node mein ek extra pointer.

DLL edit karte waqt sabse common structural bug kya hai?

Sirf do mein se ek pointer (next ya prev) update karna, jisse invariant toot jaata hai.

Connections

Singly Linked List — DLL yahi hai plus ek prev pointer.
Linked List vs Array — DLL extra memory ke badle O(1) neighbour access leta hai.
LRU Cache — O(1) tail eviction ke liye DLL + hashmap use karta hai.
Browser History — back/forward directly prev/next se map hota hai.
Circular Doubly Linked List — tail.next = head, head.prev = tail.
Big-O Notation — upar ke O(n)/O(1) costs justify karta hai.