Doubly linked list — bidirectional traversal: Visual walkthrough

Before we can delete anything, we must agree on what a "node" and an "arrow" even are. So Step 1 builds the vocabulary from zero.

Step 1 — What a node and its two arrows actually are

WHAT. A node is a little box holding three things: a data value, and two pointers. A pointer is simply an arrow that says "the box over there." One arrow is called ==next (points to the box on the right); the other is prev== (points to the box on the left).

WHY two arrows and not one? With one arrow (a Singly Linked List) you can only ever look one direction — like a kid who only holds the hand of the person in front. The second arrow is what lets you turn around cheaply. Every claim later on rests on both arrows existing.

PICTURE. Below, the box labelled B has data 20. The pale-yellow arrow leaving its right is B.next; the chalk-blue arrow leaving its left is B.prev. Read the arrow as the English sentence written under it.

Figure — Doubly linked list — bidirectional traversal

Step 2 — The invariant, drawn as two arrows that must agree

WHAT. Take any two neighbours, A and B, with A on the left. Two separate arrows describe this one adjacency: A.next points right at B, and B.prev points left at A. The rule is that these two arrows must always point at each other.

WHY. If only one of them is right, traversal lies. Walking left-to-right you'd land on B; walking right-to-left you'd skip it or land somewhere else. Consistency in both directions is the entire promise of the structure.

PICTURE. The green loop in the figure shows the round trip: leave A by next, arrive at B; leave B by prev, arrive back at A. Start and end must be the same box.

Step 3 — The goal: delete the middle box `B`

WHAT. Our list is A ⇄ B ⇄ C. We want to remove B so the list becomes A ⇄ C, and both directions of traversal still work.

WHY draw it before coding? Because "remove B" secretly means "make four arrows agree without B." Two arrows currently point at B (from A and from C); two arrows leave B. If we forget even one, the invariant from Step 2 breaks somewhere.

PICTURE. B is circled in pink — the box we intend to drop. Notice the two arrows aimed into it: A.next (yellow) and C.prev (blue). These are the two arrows we must re-route.

Recall

Before deleting a middle node, how many arrows point at it, and from where? ::: Two — A.next from the left neighbour and C.prev from the right neighbour.

Step 4 — Re-route the forward arrow: `A.next = C`

WHAT. We bend A's right-arrow so it skips B and lands on C.

WHY this one first? Because to reach C at all, we look at B.next (which still validly points to C). We must read B's links before we damage them. So the first edit uses B as a map: A.next = B.next.

PICTURE. The yellow arrow that used to end at B is redrawn (dashed = old, solid = new) to end at C. B is now unreachable going forward — but not yet backward; the blue arrow C.prev still points at B.

Step 5 — Re-route the backward arrow: `C.prev = A`

WHAT. Now bend C's left-arrow so it skips B and lands on A.

WHY. After Step 4, forward traversal is fixed but backward traversal still walks into B (a box nobody wants). We use B.prev (still pointing at A) as the map: C.prev = B.prev.

PICTURE. The blue arrow that ended at B is redrawn to end at A. Now trace both green loops: A.next=C, C.prev=A. They agree — the invariant of Step 2 holds for the new pair A,C.

Step 6 — The general delete, and why the order was safe

WHAT. Combining Steps 4–5 gives the full routine. We guard each write in case a neighbour is null.

def delete_node(x):
    if x.prev is not None:      # A exists?
        x.prev.next = x.next    #  A.next = C   (Step 4)
    else:
        head = x.next           #  x was head → new head is C
    if x.next is not None:      # C exists?
        x.next.prev = x.prev    #  C.prev = A   (Step 5)
    else:
        tail = x.prev           #  x was tail → new tail is A

WHY read-before-write matters. Both re-routes read x.next and x.prev — the arrows leaving x. We never overwrite those two arrows on x itself, so they stay valid maps for the whole routine. This is the deletion twin of the parent's insertion rule "attach before you detach": here it is "read x's links before you strand x."

PICTURE. The finished list A ⇄ C, with B floating free (garbage-collected). Both green round-trips close.

Step 7 — Every degenerate case, each with its own guard

The if/else branches above are not decoration; each covers a case where a neighbour is missing. The parent note demanded we cover all cases — here they are, drawn.

WHAT & WHY. A pointer that would be null cannot have .next or .prev written to it (that would crash / write into empty ground). So each side is guarded.

PICTURE. Four scenarios side by side:

Formula Case table

Case	`x.prev`	`x.next`	What updates
middle node	A	C	`A.next=C`, `C.prev=A`
delete head	`null`	C	`head=C`, `C.prev=null`
delete tail	A	`null`	`tail=A`, `A.next=null`
only node	`null`	`null`	`head=null`, `tail=null` (empty list)

The one-picture summary

Everything above compresses to: two arrows point at the doomed node; re-route both to point past it, reading its links before you strand it, and null-guard each end.

Recall Feynman: tell it to a 12-year-old

Three kids stand in a line — Alice, Bob, Carol — holding hands both ways: each holds the front-hand and the back-hand of their neighbour. Bob has to leave. If he just lets go, there's a hole: Alice is reaching into empty air with her right hand, Carol reaching into empty air with her left. So before Bob steps out, Alice and Carol grab each other's hands across the gap — Alice's right hand finds Carol, Carol's left hand finds Alice. Two new hand-holds, one on each side. Now Bob slips out and the line is whole: you can still walk it front-to-back or back-to-front. The one trick: Bob is the person who knows who's on each side, so you use him to find Alice and Carol before he wanders off. And if Bob was standing at the very front or very back, there's only one neighbour to fix — plus you must remember to point at the new first (or last) kid.

Connections

Parent: bidirectional traversal — this page is the deletion derived visually.
Singly Linked List — there, one arrow per node; deletion needs the previous node found by an $O (n)$ walk.
Linked List vs Array — deletion here is $O (1)$ once you hold the node; arrays shift elements $O (n)$ .
LRU Cache — evicting the tail is exactly the "delete tail" case of Step 7.
Browser History — leaving a page mid-history is a middle delete.
Circular Doubly Linked List — same two re-routes, but no null ends to guard.
Big-O Notation — the whole delete is $O (1)$ work: a fixed number of arrow re-routes.