Doubly linked list — bidirectional traversal

What is a Doubly Linked List?

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

The crucial invariant (a rule that must always hold):

$\text{for every node } x:\quad x.next.prev = x \quad\text{and}\quad x.prev.next = x$

(whenever those neighbours exist). If you ever break this, traversal lies to you.

Bidirectional Traversal — deriving it from scratch

WHAT we want: visit every node either left-to-right or right-to-left.

HOW, 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

Why cur is not None? Because the last node's next is null. Reaching None is the signal "no more nodes."

HOW, backward (tail → head):

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

Why start at tail and not head? Because going backward means following prev. We need a node at the back to begin. This is the whole payoff of storing tail: backward traversal is $O(n)$ from the start, never $O(n^2)$.

Worked Example 1 — Print forward then backward

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

Forward:

Output: 10 20 30. Why step 4? 30.next is None, so the while condition fails — that's the clean stop, no off-by-one.

Backward (start at tail=30): Output: 30 20 10, by following prev each time. Why it works: the invariant guarantees 30.prev = 20, 20.prev = 10, 10.prev = None.

Worked Example 2 — Insert in the middle (and keep the invariant)

Insert 25 between 20 and 30.

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

Why this exact order? Steps 1–2 wire new to its neighbours first, while the old links still exist. If you did step 5 (node.next = new) too early, you'd lose the pointer to 30 and couldn't reach it to fix its prev. Always attach the new node before detaching the old links.

After insertion, check the invariant: 25.next.prev = 30.prev = 25 ✓ and 25.prev.next = 20.next = 25 ✓. Bidirectional traversal now correctly produces 10 20 25 30 forward and the reverse backward.

Worked Example 3 — Reverse traversal without a tail pointer

What if you only have head? You can still go backward — but you must first walk forward to the end:

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

Why is this still fine? Total $O(n)+O(n)=O(n)$. Storing tail only saves the first walk. The prev pointers do the real work either way.

Active Recall

Connections

• Singly Linked List — DLL is this plus a prev pointer.
• Linked List vs Array — DLL trades extra memory for O(1) neighbour access.
• LRU Cache — uses a DLL + hashmap for O(1) eviction from the tail.
• Browser History — back/forward maps directly to prev/next.
• Circular Doubly Linked List — tail.next = head, head.prev = tail.
• Big-O Notation — justifies the O(n)/O(1) costs above.

Concept Map

Hinglish (regional understanding)