Foundations — Doubly linked list — bidirectional traversal

Before you can read the parent note fluently, you need to earn every symbol it uses. Below, each idea is built from nothing — plain words first, then a picture, then the reason the topic cannot live without it. Nothing is used before it is defined.

1. A "box" — the node

Picture. Look at the box below. The middle slot holds the value; the left and right slots hold arrows (we'll define those next).

Why the topic needs it. The whole list is made of nodes. If you don't picture a node clearly, every later sentence ("update the node's prev") is meaningless.

2. What a box stores — data

Picture. In figure s01, the yellow centre slot labelled data = 10 is the cargo.

Why the topic needs it. Without data, a list of boxes stores nothing useful. When the parent writes visit(cur.data), it means "look at the cargo of the current box."

3. An arrow / pointer — how one box "knows" another

Picture. The blue arrow leaving a box and landing on the next box is a pointer.

Why the topic needs it. Boxes sitting alone are just boxes. Pointers are the hands that hold them into a chain. Every "step forward" and "step back" is just following a pointer.

4. The two named pointers — next and prev

Each node in a doubly linked list carries two pointers:

Picture. Two arrows per box: a blue next arrow going right, a green prev arrow going left. This is the single feature that separates a doubly linked list from a singly linked list.

Why the topic needs it. A Singly Linked List has only next — a one-way street. Adding prev is the entire subject of this chapter: it is what makes stepping backward a single cheap move.

5. The empty pointer — null (a.k.a. None)

Picture. In figure s02 the leftmost box's green prev arrow points into empty space (null), and the rightmost box's blue next arrow points into empty space (null). Those two "nothing" arrows mark the two ends of the chain.

Why the topic needs it. Every traversal loop in the parent stops with while cur is not None. The loop is really asking "is there still a box, or did I fall off the end into null?" Without null, a walk would never know when to stop.

6. The two ends — head and tail

Picture. In figure s02, head is the arrow pointing at the leftmost box; tail is the arrow pointing at the rightmost box.

Why the topic needs it.

• To traverse forward you must know where to start → that's head.
• To traverse backward you must know where the back is → that's tail. Storing tail is what lets backward traversal begin immediately in $O(1)$ instead of first walking all the way to the end.

7. The moving finger — cur (the current node)

Picture. Picture your fingertip resting on one box. cur = cur.next slides the finger one box right; cur = cur.prev slides it one box left.

Why the topic needs it. Every loop in the parent uses cur. The line cur = cur.next reads: "move my finger to whatever next points at." When the finger lands on null, the walk is over.

8. The dot — x.next, x.prev, x.data

So x.next.prev reads left to right:

1. x.next → the box to the right of x,
2. .prev → that box's left-pointer.

Picture. Start at box x, hop right via .next, then read the green prev arrow of where you landed. If everything is wired correctly, that arrow points back at x.

Why the topic needs it. The list's core rule is written entirely in dot notation. You must be able to trace x.next.prev step by step, or the invariant below is unreadable.

9. The rule that must never break — the invariant

The DLL invariant, in the parent's notation:

In plain words: "If I step right and then look left, I must be back where I started — and vice versa." The two boxes on either side of a link must agree that they are neighbours.

Picture. Walk right along the blue arrow, then walk left along the green arrow; you must return to the same box — a closed little loop between neighbours.

Why the topic needs it. Both directions of traversal trust this rule. When you insert or delete, you must re-wire two arrows per boundary to keep it true — that's the whole reason insert_after looks fiddly.

10. The size and cost symbols — $n$, $O(\cdot )$

Three costs you will meet:

Why the topic needs it. The entire point of adding prev is a cost claim: "step back is $O(1)$, not $O(n)$." You cannot appreciate the payoff without reading these symbols.

How it all fits together

Every arrow above says "you need this before you can understand that." The bottom node is the parent topic: Doubly linked list — bidirectional traversal.

Equipment checklist

Connections

• Singly Linked List — a node here has only next; this page's prev is the one thing it adds.
• Linked List vs Array — pointers vs. index-based access; why arrows cost extra memory.
• Big-O Notation — full meaning of $O(1)$, $O(n)$, $O(n^2)$ used in the cost claims.
• Parent: Bidirectional traversal — where all these symbols are put to work.