Chapter 3 — Reps

Conditioning, not grading. Python reps this week, all about nodes, pointers, and the footrace between a linked list and an array.

Ground rules:

1. Type every line yourself. No copy-paste. Wiring pointers is a finger skill; the fingers have to learn it.
2. Run everything. Predict the output first, in writing, then run and compare. The gap between your prediction and reality is the lesson.
3. AI stays OFF. Phase 1. You cannot reason about the cost of a structure you have never built — and broken — with your own hands. Build it.
4. Measure honestly. When a rep says “time it,” use time.perf_counter(), run each measurement a few times (the first run is cold), and report the median, not the best.
5. Draw before you type. For every pointer-rewiring rep, sketch the boxes and arrows on paper first. The bugs hide in the order of the assignments.

These reps assume Python 3.10+ on your own machine (Appendix A). The chapter’s code/ folder has runnable demos referenced below.

Reps 1–3: Nodes and the Front Door

Rep 1 — Build a Node and a Prepend-Only List

From scratch, write the Node class (value + next) and a SinglyLinkedList with only __init__, prepend, and __str__:

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

Prepend 10, then 20, then 30. Predict in writing what __str__ prints before you run it. (Hint: prepend puts each new value at the front, so the order reverses.) Run it. Confirm [30 -> 20 -> 10]. Then read your prepend and write one sentence explaining why it is O(1) no matter how long the list is.

Rep 2 — Append the Slow Way, Then Time It

Add an append_slow that has no tail pointer — it walks from the head to the last node every time. Build a list of n elements with it at n = 1000, 4000, 16000 and time each.

Predict first: what shape is the cost of building n elements this way? Run it. Confirm the times grow roughly quadratically (each append is O(n), done n times = O(n²)). Write the one sentence relating your numbers to §3.2’s warning.

Rep 3 — Walk It With __iter__ and __len__

Add __len__ (must be O(1) — track _length, never recount) and __iter__ (a generator that yields each value front to back). Confirm both work:

for v in mylist:
    print(v)
print(len(mylist))

Then deliberately break __len__ by forgetting to increment in prepend. Watch len() lie. Restore it. This is the invariant you will protect all week: every insert is +1, every delete is -1, no exceptions.

Reps 4–6: The Tail Pointer and Find

Rep 4 — Add the Tail Pointer, Prove the Win

Add a _tail pointer and rewrite append to be O(1) (splice onto _tail, no walk). Be careful with the empty-list case — head and tail both become the new node.

Now race the two appends. Build n = 20000 elements with append_slow (Rep 2) and with the new O(1) append. Predict the ratio’s shape first. Run it. The O(1) version should be dramatically faster and the gap should widen as n grows — that’s the difference between O(n) and O(n²) made visible.

Rep 5 — Find, and What It Costs

Add find(value) that returns the first Node holding value, or None. Walk from the head.

Build a list [0, 1, 2, ..., 9999]. Time find(0) (front), find(5000) (middle), and find(9999) (back). Predict the pattern. Run it. Confirm that finding the last element costs far more than finding the first — there is no index arithmetic, so find is O(n) and the position matters. Write the sentence connecting this to why the array (O(1) index) crushes the list on random access.

Rep 6 — Find vs Python’s in

Compare your find against Python’s built-in in on a list of the same data:

target = 9999
# yours:
hit = mylist.find(target) is not None
# Python list:
hit = target in py_list

Both are O(n) (the Python list in also scans linearly). Time both for the worst case (target at the end), n = 100000. Predict which is faster and why. Run it. The Python list in runs in fast C; your find runs one Python attribute lookup per node. Write one sentence: same Big-O, different constant — and name the constant.

Reps 7–9: Delete, the Three Cases, and the Tail Bug

Rep 7 — Delete: Head, Tail, Middle

Implement delete(value) returning True/False. It must correctly handle all three cases: deleting the head, the tail, and a middle node — and keep _head, _tail, and _length all honest.

Build [10, 20, 30, 40, 50] and test each case:

• delete(10) (head) → [20, 30, 40, 50]
• delete(50) (tail) → check _tail now points at the node holding 40
• delete(30) (middle) → [20, 40] (after the above)
• delete(99) (absent) → returns False, list unchanged

Rep 8 — Write the Test That Catches the Tail Bug

The nastiest linked-list bug: deleting the tail without updating _tail. The list looks fine — until you append again. Write a test that catches it:

def test_delete_tail_then_append():
    s = SinglyLinkedList()
    for x in [1, 2, 3]:
        s.append(x)
    s.delete(3)           # delete the tail
    s.append(4)           # if _tail wasn't fixed, 4 is spliced onto an orphan
    assert list(s) == [1, 2, 4], list(s)   # 4 must be reachable from the head

Run it against a correct delete (passes). Then comment out the if node is self._tail: self._tail = prev line and run again. Watch it fail — the 4 vanishes. That failing test is the proof your fix matters. Restore the line.

Rep 9 — Catch an Accidental Cycle

Introduce a deliberate bug in delete: set prev.next = node (the doomed node itself) instead of prev.next = node.next. Then run list(mylist) on a 3-element list. It will hang — an infinite loop, the signature of an accidental cycle.

Kill it (Ctrl-C). Fix the bug. Write one sentence: why does a cycle make __iter__ never terminate, and what’s the one-line guard that distinguishes “end of list” from “keep going”?

Reps 10–12: Doubly Linked and the Footrace

Rep 10 — Doubly Linked, the O(1) Held-Delete

Build a DoublyLinkedList with DNode (value, next, prev), an append that returns the node, and a delete_node(node) that splices a held node out in O(1).

d = DoublyLinkedList()
handles = [d.append(x) for x in [10, 20, 30, 40, 50]]
d.delete_node(handles[2])     # remove 30 — no search, four pointer assignments
assert list(d) == [10, 20, 40, 50], list(d)

Add __reversed__ (walk from _tail via prev) and confirm list(reversed(d)) == [50, 40, 20, 10]. Write one sentence: what did the second pointer per node buy you, and what did it cost?

Rep 11 — The Footrace: Traverse and Random Access

Race your linked list against a Python list of the same n = 40000 elements.

• Traverse: sum every element of each. Predict which wins and by how much.
• Random access: pick 2,000 random indices; sum the elements at those indices in each. For the list you must walk to each index (O(n) per access); for the array it’s O(1).

Run both. The traversal will be close (in CPython, interpreter overhead and boxing mask the cache effect — see §3.6). The random access will be a massacre in the array’s favor. Write two sentences relating each result to §3.6: which row is “same Big-O, constant factor” and which is “different Big-O entirely.”

Rep 12 — The Front-Insert Win

This is the row where the linked list’s better Big-O finally pays. Race front insertion at n = 20000:

• Linked list: prepend(x) n times — O(1) each, O(n) total.
• Array (Python list): data.insert(0, x) n times — O(n) each, O(n²) total.

Predict the shape of the gap. Run it. The linked list should win by a huge margin, and the margin should grow with n (it’s a factor of n, not a constant). Write the sentence that completes the chapter’s thesis: the linked list wins when the asymptotic gap is a whole factor of n; it loses when the gap is merely a constant.

Done? One Last Thing.

From scratch, no looking — write a complete SinglyLinkedList with prepend, append (O(1), tail pointer), find, delete (all three cases), __len__, and __iter__. Then write a 6-test suite that proves:

1. A fresh list has length 0 and iterates to [].
2. After three appends, order and length are correct.
3. prepend puts the value at the front.
4. delete of the head, the tail, and a middle node each leave a correct list (and _tail correct after a tail delete — Rep 8’s bug).
5. delete of an absent value returns False and changes nothing.
6. find returns a node for a present value and None for an absent one.

Watch every test pass. If you can build the list cold, break it on purpose, and write the test that catches the break — you have the move.

Up next: Project 3 — Project 3: Linked List vs Array Benchmark.