Linked Lists

A linked list is a data structure that stores values in separate nodes, each holding one value and a next pointer to the following node. Insertion at the head costs O(1) — one pointer write — but reaching any position means walking the chain from head, so access, search, and arbitrary insertion all cost O(n) time.

Think of it as a scavenger hunt. Each clue holds one prize and tells you where the next clue is hidden. You can't jump to clue five; you follow one through four first. But slipping a new clue into the middle is trivial — rewrite two clues and nobody downstream ever knows.

How a Linked List Works

The displayed code is a singly linked list: a Node holding value and next, and a LinkedList holding one entry point, head. There is no tail pointer — insert_tail walks the whole chain every time, and the complexity table charges for it.

Every mutation is a clue splice. insert_head(v) points the new node's next at the old head, then swings head onto the new node — two writes, zero walking. insert_at(k, v) walks to position k − 1, then performs the same two writes: newNode.next = curr.next, then curr.next = newNode. The order matters (see Common Mistakes), so the animation plays the writes as separate beats.

delete(v) checks the head first — an O(1) special case, since the head has no predecessor to rewire. Otherwise curr walks while looking ahead: it probes curr.next.value, never its own, so when the target turns up, curr already stands on the predecessor — exactly where curr.next = curr.next.next needs it. search(v) is the plain walk: compare, step, return the index or -1.

One honest disclosure: the capacity slider (4–10 nodes, default 7) exists only because the canvas fits so many boxes. The code mirrors it with a max field, but a real linked list has no capacity — unbounded growth is half the point.

Linked List Operations Step by Step

The list starts empty. Run this sequence from the Inputs panel:

1. Insert Head 5 — the new node stages above the row, its next aims at the sentinel ∅ (the old head was nothing), then head swings onto it. List: 5 → ∅.
2. Insert Head 8 — node 8 stages, 8.next aims at the current head 5, then head redirects to 8. List: 8 → 5 → ∅.
3. Insert Tail 3 — curr walks: index 0 (value 8), index 1 (value 5, whose next is ∅, so the walk stops). Then 3.next = ∅ and 5.next swings to 3. List: 8 → 5 → 3 → ∅.
4. Insert At Index 1, value 7 — curr walks to the predecessor at index 0. Then 7.next = 8.next (which is 5), then 8.next = 7. List: 8 → 7 → 5 → 3 → ∅.
5. Search 5 — probe index 0: 8 ≠ 5; index 1: 7 ≠ 5; index 2: 5 = 5. Found at index 2.
6. Delete 5 — head check: 8 ≠ 5. Look-ahead walk: curr at index 0 probes 7 ≠ 5; at index 1 probes 5 = 5. Node 5 lifts out, 7.next bypasses it to 3, the chain closes. List: 8 → 7 → 3 → ∅.

On the canvas, the curr cursor marks each probe, a staged node hovers above its slot until both pointer writes land, and a deleted node lifts out while the bypass arrow swings past it — the two-writes-then-commit rhythm above, drawn one beat at a time.

Time and Space Complexity

A tail pointer would make tail insertion O(1); the code skips it to keep the walk visible. The time complexity of the splice itself is always O(1) — you only pay for getting there.

Edge Cases

• Insert into an empty list — head and tail insertion collapse into the same move: head swings from ∅ onto the lone new node.
• Delete or search on an empty list — both return gracefully (False / -1) via the if not self.head guard. No exception.
• Delete the head — caught by the O(1) head check; head = head.next, no walk.
• Delete a missing value — curr.next hits ∅ and the guard returns False.
• insert_at(k, v) with k past the end — the code has no bounds check and would walk off the chain into a crash; the visualization stops and says so instead. (k = 0 simply delegates to insert_head.)

Common Mistakes

• Splicing in the wrong order. Write newNode.next = curr.next before curr.next = newNode. Reversed, you overwrite the only clue pointing at the rest of the hunt — the back half of the list is gone.
• Hunting the node instead of its predecessor. The rewire needs the node before the target — which is why the delete walk probes curr.next, not curr.
• Off-by-one in the walk condition. while curr.next stops on the last node (what tail insertion wants); while curr inspects the last node too (what search wants). Swap them and you skip the final node or dereference ∅.
• Using a linked list when an array would do. Pointer-chasing through scattered memory is brutal on caches. Pick the list when you splice in the middle often and rarely access by index; otherwise the boring contiguous array wins.