Doubly linked list — bidirectional traversal: Worked examples

This is the "throw everything at it" page for the parent topic. A doubly linked list (DLL) — a chain of nodes, where each node stores a data value, a next pointer to the node in front, and a prev pointer to the node behind — looks simple. But the bugs live in the edge cases: empty lists, single nodes, the very first node, the very last node. Below we hunt down every one.

The scenario matrix

Every structural operation on a DLL falls into one of these case classes. The columns are the two things that decide whether code breaks: does a left neighbour exist? and does a right neighbour exist?

#	Case class	Left neighbour (`prev`)	Right neighbour (`next`)	What can go wrong
C1	Empty list	—	—	`head`/`tail` are `null`; a naive `head.next` crashes
C2	Single node	`null`	`null`	node is both head and tail at once
C3	Operate at head (front)	`null`	exists	must update `head`, careful with `prev = null`
C4	Operate at tail (back)	exists	`null`	must update `tail`, careful with `next = null`
C5	Operate in the middle	exists	exists	must fix four pointers
C6	Traverse forward & backward	—	—	choosing the right start node & stop signal
C7	Limiting / cost behaviour	—	—	how time grows as $n \to$ large
C8	Real-world word problem	—	—	mapping a story to head/tail moves
C9	Exam twist	—	—	subtle off-by-one / wrong-condition trap

Below, 9 worked examples hit every cell C1–C9. Each is labelled with its cell.

Example 1 — Insert into an EMPTY list · cell C1

Forecast: guess first — how many pointers point to the new node when it is the only node?

Steps

Create new with new.data = 5. Why this step? Nothing to link yet; we make the object before wiring it.
Set new.prev = null and new.next = null. Why this step? A lone node has no neighbours on either side, so both pointers are the "nothing here" value null.
Set head = new and tail = new. Why this step? With one node, that node is simultaneously the first and the last — so both list-level pointers must reference it. Forgetting tail here is the classic C1 bug.

Verify: After insertion, head == tail (both point at node 5), head.prev == null, tail.next == null. Traverse forward → 5; traverse backward → 5. One node, printed once in each direction. ✓

Example 2 — Insert at the FRONT of a single-node list · cells C2, C3

Forecast: which two nodes change a pointer, and does tail move?

Steps

Create new, new.data = 10. Why? Build before wiring (our rule "attach before you detach").
new.prev = null; new.next = head (i.e. new.next = node(20)). Why? The new front node has no one behind it (prev = null) and the old head in front of it.
head.prev = new (i.e. node(20).prev = node(10)). Why? The invariant demands 20.prev.next = 20; wiring 20.prev = 10 and 10.next = 20 makes both directions agree.
head = new. Why? The first node changed, so the list-level head pointer must follow.

Note we did not touch tail: node 20 is still the last node.

Verify: Forward 10 20, backward 20 10. Check invariant at the seam: 10.next.prev = 20.prev = 10 ✓ and 20.prev.next = 10.next = 20 ✓. head.prev = null ✓, tail.next = null ✓.

Example 3 — Insert at the BACK (append) · cell C4

Forecast: which of head/tail moves, and is any pointer set to null?

Steps

Create new, new.data = 30.
new.next = null; new.prev = tail (= node(20)). Why? A new tail has no one in front (next = null); behind it is the old tail.
tail.next = new (node(20).next = node(30)). Why? Complete the two-way link so 20.next.prev = 30.prev = 20 holds.
tail = new. Why? The last node changed; update the list-level tail.

Verify: Forward 10 20 30, backward 30 20 10. Seam invariant: 20.next.prev = 30.prev = 20 ✓, 30.prev.next = 20.next = 30 ✓.

Example 4 — Insert in the MIDDLE · cell C5 (the four-pointer case)

Forecast: how many pointer assignments does the middle case need? (Count them before reading.)

Steps (let L = node(20) = left neighbour, R = node(30) = right neighbour)

Create new, new.data = 25.
new.prev = L (25.prev = 20). Why? Wire new node to left, while old links still exist.
new.next = R (25.next = 30). Why? Wire new node to right, while old links still exist.
L.next = new (20.next = 25). Why? Redirect the left neighbour forward onto the new node.
R.prev = new (30.prev = 25). Why? Redirect the right neighbour backward onto the new node.

That is four pointer writes (steps 2–5). The middle case is the only one that touches four; that is why it's the most bug-prone. Steps 2–3 (attach) come before steps 4–5 (detach the old direct 20↔30 link) so we never lose a reference.

Verify: Forward 10 20 25 30, backward 30 25 20 10. Both seams: 25.next.prev = 30.prev = 25 ✓, 25.prev.next = 20.next = 25 ✓.

Example 5 — Delete the ONLY node → back to empty · cells C2 → C1

Forecast: after deleting the last remaining node, what are head and tail?

Steps

Notice head == tail and node.prev == node.next == null. Why? This is the single-node signature — a special case, not the general one.
Set head = null and tail = null. Why? With the sole node gone, there are no nodes, so both list pointers become null. Updating only head and forgetting tail leaves a dangling tail pointing at freed memory — a C1/C2 boundary bug.

Verify: List is empty. Traverse forward → prints nothing (loop never enters because head is None). Traverse backward → prints nothing. Round-trip: Example 1 then Example 5 returns to the start state. ✓

Example 6 — Delete a MIDDLE node · cell C5

Forecast: to remove a middle node, whose pointers must be stitched together across the gap?

Steps (let x = node(30), so x.prev = node(20), x.next = node(40))

x.prev.next = x.next (20.next = 40). Why? Bridge the left neighbour forward over the hole to the right neighbour.
x.next.prev = x.prev (40.prev = 20). Why? Bridge the right neighbour backward over the hole to the left neighbour. Both directions must be re-linked or the invariant breaks.
(Optional) clear x.prev = x.next = null so the removed node can't be followed back in.

Verify: Forward 10 20 40, backward 40 20 10. New seam: 20.next.prev = 40.prev = 20 ✓, 40.prev.next = 20.next = 40 ✓. Length dropped from 4 to 3.

Example 7 — Full bidirectional traversal & its cost · cells C6, C7

Forecast: if you print in both directions, is total work $O (n)$ or $O (n^{2})$ ? Guess.

Steps

Forward: cur = head; loop while cur is not None, visit, then cur = cur.next. Why the stop condition? 40.next = null, and reaching null is the clean "no more nodes" signal — no off-by-one. Output: 10 20 30 40 — that is 4 visits.
Backward: cur = tail; loop while cur is not None, visit, then cur = cur.prev. Why start at tail? Backward means following prev; you need a node at the back to begin. Output: 40 30 20 10 — another 4 visits.
Total visits $= 4 + 4 = 8$ . Why? Each pass touches each node once: $n + n = 2 n$ .
As $n$ grows, $2 n$ is still linear: $cost = 2 n = O (n) .$ Why not $O (n^{2})$ ? Because we never restart from the head inside the backward pass — the prev pointers let each step be $O (1)$ . (In a Singly Linked List with no prev, backward printing forces a restart per node → $O (n^{2})$ .)

Verify: With $n = 4$ : forward visits $= 4$ , backward visits $= 4$ , total $= 8 = 2 n$ . See Big-O Notation for why the constant $2$ drops out.

Example 8 — Real-world word problem: Browser back/forward · cell C8

Forecast: when you go Back and then visit a new page, what happens to the pages that were "in front"?

Steps

Start: A ⇄ B ⇄ C, cur = C.
Back → cur = cur.prev = B. Why $O (1)$ ? One prev hop — the whole point of storing prev.
Back again → cur = cur.prev = A. Why? Same one-hop move; two Backs = two hops.
Visit new page D: everything after cur is discarded, then D is appended after cur.
- Detach cur.next (B and C are dropped): A.next = D, D.prev = A, D.next = null, tail = D. Why discard forward history? Browsers throw away the "forward" pages once you branch — exactly deleting the sublist to the right of cur, then appending.
Now cur = D.

Verify: Final list A ⇄ D. Forward A D, backward D A. Pages B and C are unreachable (gone). Seam: A.next.prev = D.prev = A ✓, A.prev = null ✓ (A is head), D.next = null ✓ (D is tail).

Example 9 — Exam twist: the wrong loop condition · cell C9

Worked example Statement

A student writes this to print all nodes of 10 ⇄ 20 ⇄ 30:

cur = head
while cur.next is not None:   # BUG
    visit(cur.data)
    cur = cur.next

What does it print, why, and what is the one-character-idea fix?

Forecast: predict the output before reading. (Does 30 get printed?)

Steps

cur = 10. Condition 10.next is not None → 20 exists → true. Print 10. Move to 20.
cur = 20. 20.next is not None → 30 exists → true. Print 20. Move to 30.
cur = 30. 30.next is not None? 30.next = null → false → loop exits without printing 30. Why? The condition tests the node ahead, so it stops one node early — an off-by-one that silently drops the last node.
Fix: test the current node, not the next: while cur is not None:. Why? Now the loop runs for the last node and only stops when cur itself falls off the end into null.

Verify: Buggy version prints 10 20 (2 nodes). Corrected version prints 10 20 30 (3 nodes). The condition while cur.next is not None is correct only when you deliberately want to stop at the last node — e.g. to find the tail.

Coverage check — did we hit every cell?

Recall Matrix cell → example map

C1 empty ::: Examples 1 & 5 C2 single node ::: Examples 2 & 5 C3 head/front ::: Example 2 C4 tail/back ::: Example 3 C5 middle (4 pointers) ::: Examples 4 & 6 C6 traverse both ways ::: Example 7 C7 limiting cost O(n) ::: Example 7 C8 real-world word problem ::: Example 8 C9 exam twist ::: Example 9

Active Recall

Related structures & uses: Circular Doubly Linked List, LRU Cache, Linked List vs Array.

Connections

Doubly linked list — bidirectional traversal — the parent this page drills into.
Singly Linked List — no prev, so backward printing is $O (n^{2})$ (Example 7).
Browser History — the back/forward model of Example 8.
LRU Cache — head/tail edits (Examples 3–6) power $O (1)$ eviction.
Big-O Notation — why $2 n = O (n)$ in Example 7.