Project 3 — Linked List vs Array Benchmark

“For just as the body is one and has many members, and all the members of the body, though many, are one body, so it is with Christ.” — 1 Corinthians 12:12

Chapter: 3 — Linked Lists and the Cost of Pointers Due: End of Week 3 Submit: A link to a public GitHub repo containing linked_list.py, your test file, benchmark.py, the benchmark results, and README.txt. Real toolchain, real git — see Appendix A for the Python + git setup. Allowed tools: Python 3.10+, the standard library (time, sys, unittest/pytest, random), a real editor, the textbook, your own DynamicArray from Project 2, and the given array_front_insert.py in this chapter’s code/ folder (the front-insert array you’re handed — see the front-insertion workload below). No external packages, no IDE running for you, no internet during the build. AI: Phase 1 (wk 1–8): AI is OFF. No assistants, no autocomplete-beyond-a-word, no “explain this.” You cannot judge the cost of a structure you have never built and raced yourself — and the whole point of this project is to feel the gap between “O(1) insert” and “actually wins the race,” so that in Phase 2 you can direct an agent and know when its data-structure choice was wrong. Phase 2 (wk 9–16) turns agentic AI on and requires an agent-log.txt. Not yet.

The Setup

A ministry runs a long-lived event service. As people arrive, items stream in — check-ins, prayer requests, song requests — and a lead developer reached for a linked list because “everyone knows linked lists are O(1) to insert, and an array has to shift everything.” The service has gotten slow. The “fast” structure is, somehow, the slow part. The team is confused: the Big-O on the whiteboard clearly favors the linked list.

You’ve been brought in to settle it the only way it can be settled — by measurement.

You will build a singly linked list by hand, race it against your dynamic array from Project 2 across the workloads the service actually runs, and write the memo that tells the team the truth: where the linked list’s celebrated O(1) operations genuinely win, where they lose despite the asymptotics because every node is a scattered heap allocation that pointer-chases across cache lines, and which structure their actual workload deserves. This is the chapter’s whole lesson made into a deliverable: Big-O describes how cost grows; it does not describe how much it is, and the constant factor decides real races.

You are the architect. The team has the Big-O. You bring the numbers.

Learning Targets

By completing this project, you will demonstrate that you can:

• Implement a singly linked list by hand — nodes, head/tail pointers, prepend, append, find, delete, __len__, __iter__ — keeping head, tail, and length as honest invariants.
• Implement the three delete cases (head, tail, middle) correctly, including the tail-pointer fixup.
• Build a fair benchmark harness that races two structures across multiple workloads with honest timing.
• Distinguish, in measurements, a same-Big-O-different-constant result from a different-Big-O result.
• Implement a doubly linked list and demonstrate the one workload it genuinely wins — the O(1) held-node delete — in numbers (Medium).
• Write an architectural memo that makes a tool choice from your own data and names where cache locality made the “worse” structure win (Hard) — the Phase 1 deliverable.

Normal Tier

Goal: Implement a singly linked list, test it, and race it against a dynamic array across four workloads — your own DynamicArray from Project 2 where its operations suffice, and the given array_front_insert.py for the one workload that needs a front insert Project 2’s Normal tier didn’t ask you to build (details under Required features, item 4).

Required features

1. Node — a class with value and next (use __slots__). Nothing more.

2. SinglyLinkedList with:

   • prepend(value) — O(1) front insert.
   • append(value) — O(1) back insert, using a tail pointer (no walking).
   • find(value) — return the first node holding value, or None. O(n).
   • delete(value) — delete the first node holding value; return True/False. Handle head, tail, and middle correctly; keep _tail and _length honest.
   • __len__ — O(1).
   • __iter__ — yield each value front to back.
   • __str__ — readable, e.g. SinglyLinkedList([10 -> 20 -> 30]).

3. Tests (unittest or pytest), at least 8, proving:

   • Empty list: length 0, iterates to [].
   • prepend puts the value at the front.
   • append keeps order and is reachable from the head.
   • All three delete cases, plus the tail-delete-then-append test (the bug from §3.8 / Rep 8).
   • delete of an absent value returns False and changes nothing.
   • find returns a node for present values, None for absent.

4. Benchmark harness (benchmark.py) that races your SinglyLinkedList against a dynamic array across four workloads, timing each fairly (median of ≥3 runs, time.perf_counter):

   • Random access — sum the elements at 2,000 random indices.
   • Front insertion — insert n elements at the front.
   • Back insertion (build) — append n elements.
   • Full traversal — sum every element.

   Which array do you race? Three of these four workloads (random access, back insertion, full traversal) need only append, get, __len__, and __iter__ — exactly what Project 2’s Normal tier had you build, so your own DynamicArray covers them. The front-insertion workload, though, needs an array that can insert at the front, and Normal-tier Project 2 only asked for append (insert at the back). So you don’t have to go back and add a method, this chapter’s code/ folder gives you array_front_insert.py — a complete DynamicArray with append, get, __len__, __iter__, and an O(n) insert_front. Import that for the benchmark. (If you did Project 2’s Medium tier, you already wrote insert(0, value), which is a front insert — you may race your own array instead; insert_front(value) is just insert(0, value) renamed. Either path is full credit; say which you used in your README.)

5. Results captured — a results.xlsx (or a results table in your README) with your machine’s numbers and n, plus one sentence per workload explaining the outcome in terms of Big-O and the constant factor.

Example output

Linked list vs dynamic array, n = 40,000

BUILD (append n elements):
  dynamic array .append            6.40 ms
  linked list .append              8.94 ms
  -> same Big-O; array wins the per-element constant cost.

TRAVERSE (sum every element):
  dynamic array (contiguous)       1.69 ms
  linked list (pointer-chase)      1.57 ms
  -> same Big-O; ~tie in CPython (interpreter overhead masks the cache effect).

RANDOM ACCESS (2,000 random reads):
  dynamic array O(1)/access        0.10 ms
  linked list O(n)/access        470.37 ms
  -> different Big-O; the array dominates.

FRONT INSERT (insert n at the front):
  dynamic array O(n)/insert     7457.46 ms
  linked list O(1)/insert          4.31 ms
  -> the list's better Big-O finally pays: O(n) total beats O(n^2).

Normal-tier rubric (out of 100)

Medium Tier (+up to 25% extra credit)

M1. Doubly linked list

Implement a DoublyLinkedList with DNode (value, next, prev), append/prepend that return the node, delete_node(node) (O(1) splice of a held node), __iter__, and __reversed__. Test it, including the held-delete and the backward traversal.

M2. The held-delete win, in numbers

Add a fifth workload to your benchmark: delete a node you already hold a reference to. Race the doubly linked list’s O(1) delete_node against the array’s O(n) delete-at-index (which must shift every element after the gap left to close it). Time many deletes of each. Show the win — it should be a wall-clock chasm (milliseconds vs seconds at a few tens of thousands). Add the row to results.xlsx with the one-sentence explanation: this is the one workload the linked list genuinely wins, on Big-O and constant factor both.

M3. The memory cost of the second pointer

Measure (with sys.getsizeof, accounting for __slots__) the per-node memory of a singly vs doubly linked node, and report the total extra memory the doubly linked list costs at n = 1,000,000. State the trade in one sentence: what the second pointer buys (O(1) held-delete, backward walk) and what it costs (an extra reference per node).

Hard Tier (+up to 25% additional extra credit)

H1. The architect’s memo

Write MEMO.docx (one page, ~500–700 words) addressed to the ministry’s team. Using your own measurements, answer:

1. For which specific, realistic workloads would you choose a linked list over a dynamic array? Name at least two concrete scenarios (e.g., an LRU cache that splices held nodes; a front-insert-heavy log with no random access). Cite your numbers.
2. For which would you not? Name at least two (e.g., anything index-heavy; anything build-then-iterate). Cite your numbers — especially the random-access massacre.
3. Where did cache locality (or per-node allocation) make the asymptotically “worse” structure win? Point at the exact row in your results and explain the constant factor. Be honest about the CPython traversal nuance: the cache effect is real but masked at the interpreter layer (§3.6) — say so, and say how the answer would change in C.
4. What does the ministry’s actual service deserve, and why? Make the call. Defend it with constraints, not vibes.

The memo is the heart of this project. The code proves you can build; the memo proves you can decide. An agent cannot write this memo for you — it has never run your benchmark on your machine.

H2. Make the benchmark fair and defend it

A naive benchmark lies. Audit your own harness for at least three fairness traps and document how you handled each in MEMO.docx or a BENCHMARK_NOTES.txt:

• Warm-up / cold cache — first run is slow; take the median, discard the cold run.
• Construction cost bleeding into the measured op — build the structure outside the timed region; time only the operation under test.
• Garbage-collection pauses — consider gc.disable() around a measured region (and re-enable it after), and note whether it changed your numbers.
• n too small to see the asymptotics — show at least one workload at two or three sizes so the shape (constant vs linear vs quadratic) is visible, not just one data point.

H3. The crossover point

For the front-insert workload, find (by measuring at several sizes) the approximate n at which the linked list overtakes the array — the crossover point where the O(n) total finally beats the O(n²) total. Plot or tabulate it. Write one paragraph: below the crossover, the array’s constant-factor advantage wins despite the worse Big-O; above it, the asymptotics take over. This is the most important single idea in Phase 1 — Big-O tells you who wins eventually; measurement tells you when “eventually” arrives.

Submission

Submit one URL — a public GitHub repo (see Appendix A for git setup).

What the repo must contain

1. linked_list.py — your SinglyLinkedList (and DoublyLinkedList for Medium+).
2. The array the benchmark imports — either the given array_front_insert.py (copy it into your repo), or your own Project 2 dynamic_array.py if it has a front insert (insert(0, value) from Project 2 Medium). Whichever you race, commit it so python3 benchmark.py runs from a clean checkout.
3. test_linked_list.py — the test suite. Confirm it passes before submitting.
4. benchmark.py — the harness. Runnable with python3 benchmark.py.
5. results.xlsx — your machine’s numbers, n, and one sentence per workload.
6. MEMO.docx — for Hard tier, the architect’s memo.
7. README.txt — your reflection:

# Project 3 — Linked List vs Array Benchmark

**Tier targeted:**  Normal / Medium / Hard
**Features done:**  (list)
**Headline result:**  (one line — which structure won which workload, and the surprise)
**The one place the list genuinely won:**  (which workload, and the numbers)
**The place asymptotics lied at my scale:**  (which row, and why — cache / allocation)
**What I learned:**  (one paragraph)
**What I'd change:**  (one sentence)
**AI usage:**  NONE — Phase 1.  Signed: <your name>

8. Reflection comment block at the top of benchmark.py — condensed version of the README fields.
9. The benchmark left runnable — python3 benchmark.py produces your results table from a clean checkout.

Hints (Read Before You Begin)

• Build the list first, race second. Get linked_list.py passing every test before you write a single line of benchmark.py. A benchmark of a buggy list measures nothing.
• Draw the pointers. Every insert and delete is a small sequence of pointer assignments, and the order matters. Sketch boxes and arrows on paper before you type — especially for delete’s three cases and the doubly linked delete_node.
• Keep the invariants honest. After every operation, _head, _tail, and _length must all be correct. The tail-delete bug (§3.8) is the classic; write Rep 8’s test early and let it guard you.
• Time only the operation, not the setup. Build the structures before t0 = perf_counter(). If your “front insert” timing includes constructing the array each run, you’re measuring the wrong thing.
• Take the median, discard the cold run. The first run warms the caches and the interpreter. Run each measurement at least three times; report the median.
• Be honest about the traversal tie. In CPython the linked list won’t lose traversal by much — the interpreter overhead and int boxing mask the cache effect (§3.6). Report what you measured, not what the textbook predicted. That honesty is the assignment.

What Mastery Looks Like (Beyond the Rubric)

A great Project 3 does not just confirm the textbook — it complicates it, with evidence. The student who masters this project can say, in one breath: “Linked lists are O(1) to insert at the front, and that win is real exactly when the asymptotic gap is a whole factor of n — like front-insert-heavy workloads with no random access — and exactly when you already hold the node you want to splice, which is O(1) on a doubly linked list and O(n) on an array. For everything else — random access, build-then-iterate, membership tests — the array’s contiguity and bulk allocation win the constant-factor war even where the Big-O is tied, so in Python you just use a list. And I can show you the numbers for each.”

That sentence is the chapter. A student who can say it and back every clause with their own measurement has stopped reciting Big-O and started architecting with it.

A great memo makes a call. It does not hedge into “it depends” and stop. It says: given this service’s workload — streaming appends, occasional reads by position, no held-node splicing — the array (a Python list) is the right tool, and here are the three measured rows that prove the linked list would be slower; the team’s intuition was right about the Big-O and wrong about the constant factor. That is what an architect delivers.

Coach’s Note — The first time a student watches the “fast” structure lose the race by a factor of a thousand on random access, something clicks that no lecture can install: Big-O is a tool, not a god. It tells you the shape of the cost as n grows. It does not tell you the size of the cost at the n you actually have. The architect carries both — the asymptotic shape and the measured constant — and the whole rest of this book, every database index and every server choice, is you carrying both at once. This project is where you first feel the weight of it in your own hands.

When You’re Done

1. Run your test suite. Confirm every test passes, including the tail-delete-then-append test.
2. Run python3 benchmark.py from a clean checkout. Confirm the results table prints.
3. Read your results.xlsx aloud. Could a teammate who never saw your code learn, from it alone, which structure to choose for which workload? If not, rewrite the sentences.
4. (Hard) Read your MEMO.docx as if you were the lead developer who chose the linked list. Does it change your mind? If it wouldn’t, it isn’t done.
5. Commit, push, submit the repo URL.
6. Read Chapter 4 — stacks, queues, and deques, where the same data sits on an array or a linked list and the backing choice becomes a real tradeoff you’ll get to make.

A theological footnote. Paul’s image is the body: many members, one body, joined and interdependent — “the eye cannot say to the hand, ‘I have no need of you’” (1 Corinthians 12:21). A linked list is the most literal picture of that joining in all of computing: separate nodes, each holding the next, made one sequence only by the connections between them. And there is a cost to the joining — a pointer per link, a cache miss per step, an allocation per node. The architect names that cost honestly and chooses with eyes open, because pretending the joining is free is how the ministry’s “fast” service got slow. Count the cost of the connection. Then build the body well.

See you next week.