Linked Lists
- Build singly linked lists from node objects and traverse them without losing the head
- Explain the array-vs-linked-list trade: O(1) index vs O(1) splice
- Reverse a linked list iteratively with the three-pointer dance
- Detect a cycle with Floyd's fast/slow pointers and explain why they must meet
- Sketch how a dict + linked list combine into an LRU cache
| Spaced-rep warm-up: Days 23–25 cards + due deck | 10 min |
| ELI5 + tech read, watch the linked-list visualizer | 20 min |
| Guided: build/splice + reversal dance + cycle detector | 35 min |
| Practice: merge sorted lists + Floyd vs seen-set | 20 min |
| Project: pattern log + LRU sketch | 20 min |
| Quiz + flashcards | 10 min |
Builds on: Day 9 — Object-oriented Python — classes & references · Day 22 — Big O & complexity · Day 24 — Fast/slow pointers
A treasure hunt: the first clue is in your hand, and each clue names WHERE THE NEXT ONE IS. Clue 1 → under the bridge; there you find clue 2 → inside the oak. You cannot jump to clue 7 — you must walk the chain. That is a linked list: each node holds a value and a pointer to the next node, and all you ever hold is the first clue (the head). Lose the head, lose the whole hunt.
Why organize anything this way, when numbered shelves (Day 23's arrays) let you jump anywhere instantly? Because of what INSERTING costs. Adding a shelf in the middle of a numbered warehouse means renumbering — shifting — everything after it. Adding a clue mid-hunt costs almost nothing: write one new clue, and change ONE existing clue to point to it. Nobody else in the chain even notices. That's the trade in full: arrays are instant to *read anywhere*, expensive to *splice*; linked lists are expensive to read anywhere, instant to splice — once you're standing at the right spot. Today's classic moves — reversing the hunt, detecting a prankster's clue-loop — are really exercises in pointer surgery: relinking "next" arrows without ever dropping the chain.
Honestly: you will rarely hand-build a linked list in production Python. You learn them for two real reasons. First, they are the purest gym for reference reasoning — the "names are pointers" model from Day 9 under load — and interviewers use them precisely because pointer bugs are unfakeable; reverse-a-list and detect-cycle remain screening staples. Second, the structure lives inside things you WILL use: deque (yesterday), the LRU caches behind functools.lru_cache (Day 12) and every serious caching layer (Day 47, Day 156) — dict for O(1) find + linked list for O(1) reorder is a genuinely great design you should be able to sketch.
The treasure hunt — each node only knows the next clue
step 1 / 6A linked list: each node holds a value and a pointer to the next node. No indexes, no shelf — to reach anything you follow clues from head.
Guided practice
Build, traverse, splice
15 min- In
linked_lab.py, defineListNodeand two helpers you will reuse all day:from_list(values)building a chain from a Python list, andto_list(head)doing the reverse. Test that they round-trip. - Write
insert_after(node, val)— two assignments — and in a comment explain what breaks if you swap their order (draw the arrows if it helps). - Write
delete_after(node)(one assignment: route around the victim). Note the asymmetry: with only "next" pointers, deleting a node you are STANDING ON requires knowing its predecessor — walk from the head or use a dummy. - Use the dummy-head trick to write
delete_value(head, val)that works even when the head itself must go. Test deleting the head, a middle node, and a missing value.
The reversal dance + the cycle detector
20 min- Implement
reverse(head)from the tech section — but FIRST hand-trace it on paper for the 3-node list [1, 2, 3]: draw all three arrows at each of the three iterations. The paper trace is the exercise; the code is its transcript. - Test: reverse of [1..5], of [1], and of [] (None in, None out).
- Implement
has_cycle(head)with Floyd's fast/slow. Build a test cycle by hand: make the tail's next point at the second node. (Careful: to_list on a cyclic list runs forever — that is the point.) - In a comment, write the meeting argument in your own words: in a cycle, the gap between fast and slow shrinks by exactly 1 per step, so it reaches 0 — no skipping over.
- Also write
find_middle(head)in 5 lines: when fast hits the end, slow stands at the middle. Two uses of one pattern in one day.
On your own
Merge, and the space trade
20 min(1) Merge two sorted lists into one sorted list by relinking existing nodes (no new nodes, no value copying). Use a dummy head and a tail pointer; state the complexity.
(2) Re-implement has_cycle_set(head) using a Day 23 seen-set of nodes, then write a three-sentence comparison: what does Floyd save, what does the set version win on (simplicity? finding WHERE the cycle starts?), and which would you write under interview pressure?
Hints: for (1) the loop compares the two current heads, links the smaller to the merged tail, and advances that list; when one list runs out, link the survivor whole — do not walk it.
Pattern log: pointer surgery + the LRU sketch
Add the "Linked Lists" section to patterns.md: the array-vs-list trade table (index, search, splice-at-known-node, memory locality), your solved problems (delete-with-dummy, reverse, cycle, middle, merge) each with its one-line trick, recognition cues ("reverse in place", "cycle", "middle of", "merge lists", "O(1) removal"), and honest costs (O(n) access, cache-unfriendly memory scatter, Python overhead per node). Then the capstone of the section: a half-page LRU cache design sketch — a labeled drawing (ASCII art is fine) of dict + doubly-linked list, and a table showing get/put/evict all hitting O(1), with one sentence each on which structure provides it. Commit.
Common mistakes & misconceptions
- Losing the head: advancing your only reference during traversal, then having nothing to return. Keep a separate cursor name (node = head), or use a dummy whose .next you return.
- Flipping current.next before saving current.next. The three-pointer dance exists because that one assignment destroys your only route forward — save nxt first, always.
- Comparing nodes with == when you mean identity. Two nodes can hold equal values; cycle detection asks "same NODE?" — use `is`.
- Forgetting the null guards in fast/slow: fast and fast.next must both be checked before fast.next.next, or odd-length lists crash with AttributeError on None.
- Special-casing the head in insert/delete instead of using a dummy node. The dummy costs one line and deletes an entire class of off-by-one bugs.
- Concluding linked lists beat arrays because "insert is O(1)". That O(1) requires already standing at the splice point; finding it is O(n). Arrays with their cache-friendly layout win most real workloads — know the trade, not the slogan.
Q1. In the iterative reversal loop, why must nxt = current.next happen before current.next = prev?
Q2. Why must fast and slow pointers meet if the list has a cycle?
Q3. An LRU cache needs O(1) get AND O(1) update of usage order. The classic design is…
Go deeper — curated resources
- Reverse a linked list recursively — A perfect bridge to tomorrow: the recursive reversal is 5 lines, and understanding where the "work" happens (after the recursive call returns) previews the call-stack thinking Day 27 makes explicit.
- All lab asserts pass, including the manufactured cycle
- Reversal hand-trace on paper completed before coding
- Merge relinks nodes without copying; comparison paragraph written
- patterns.md section + LRU sketch committed; quiz ≥ 2/3
← Back: Nodes are Day 9's objects; every .next is Day 9's "names are references" made structural. Fast/slow arrived on Day 24 as an array trick — today it earned its fame. The seen-set alternative is Day 23 again.
Forward →: Day 27's recursion traverses these same chains implicitly via the call stack. Trees (Day 29) are nodes with TWO nexts. The LRU sketch becomes working code when caching gets serious on Day 47 and pays LLM bills on Day 156.
Unlocks: D29 Binary Trees & BSTs