Chapter 3 — Linked Lists and the Cost of Pointers

“All problems in computer science can be solved by another level of indirection.” — David Wheeler

“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

Why This Matters

Last week you built the array and saw through it. You learned that contiguity buys you O(1) indexing and a standing gift from the cache, that append is amortized O(1) because doubling banks the cost of the rare resize across many cheap writes, and that the array’s one real weakness is its middle: insert or delete anywhere but the end and you pay O(n) to shift everyone over. We ended Chapter 2 with a cliffhanger. When the workload is full of front-and-middle insertion, the array’s O(n) middle hurts — and there is a structure that claims it can do those operations in O(1).

That structure is the linked list, and this week you build it.

The linked list is built on the single most important idea in all of programming: indirection. Instead of laying values side by side in one contiguous block, you scatter them anywhere in memory and connect them with pointers — each element carries a pointer to the next one. You already know pointers in your bones from Coding 1. In C++ you wrote Node* next; and managed the memory yourself with new and delete. In Java a node was an object holding a Node next reference, and the garbage collector cleaned up. The linked list is nothing more than that idea, repeated: a chain of small objects, each pointing at the next, strung together into one logical sequence. Many members, one body.

Here is the famous claim, and it is the reason every data-structures course teaches the linked list: inserting at the front of a linked list is O(1). No shifting. You make a new node, point it at the old head, and move the head pointer. One, two, three — done, no matter how long the list is. The array could never. To put something at the front of an array, every existing element shifts right one slot: O(n). On the asymptotic scoreboard, the linked list wins front-insertion in a landslide.

And yet. This is the chapter where you learn the thing almost no one is taught: the linked list usually loses the footrace anyway. Not because the Big-O is wrong — it’s exactly right — but because Big-O measures how cost grows, not how much it is. Every node in a linked list is a separate object allocated somewhere on the heap, scattered. Walking the list means chasing pointers from one scattered location to the next, missing the cache line bet on almost every step (recall §2.2). The array, with its contiguous layout, is kind to the cache; the linked list is hostile to it. So when you actually race them — same Big-O on traversal, “better” Big-O for the list on front-insert — the array wins most realistic workloads by a constant factor large enough to swamp the asymptotic story at every size you’ll ever see in practice.

The Christian question for the week is the body’s question, from Paul to the Corinthians: how are many members joined into one body? The linked list is the most literal answer in all of computer science — many separate nodes, each holding the next, joined into one sequence by the connections between them. It is also a lesson in honesty about cost. The textbook says “O(1) insert” and stops. The architect says “O(1) insert and here is the constant factor that decides who actually wins.” This week you will measure that constant factor with your own hands, and you will never again trust an asymptotic claim without asking what it costs in the real machine.

3.1 — Nodes and References: The Whole Idea

Strip the linked list to its atom and you find one thing: the node. A node is a value plus a pointer to the next node. That’s it. That is the entire structure, repeated.

You have built this before, in two languages, with the memory model fully visible.

In C++, a node was a struct you allocated by hand:

struct Node {
    int value;
    Node* next;   // a raw pointer to the next node, or nullptr at the end
};

Node* a = new Node{10, nullptr};   // allocate on the heap
Node* b = new Node{20, nullptr};
a->next = b;                       // link a to b
// ... and later you MUST: delete a; delete b;  (or you leak)

In Java, a node was an object holding a reference, and the garbage collector freed it for you:

class Node {
    int value;
    Node next;          // a reference to the next node, or null at the end
    Node(int v) { value = v; }
}

Node a = new Node(10);
Node b = new Node(20);
a.next = b;             // link a to b; no manual delete — GC handles it

In Python, a node is the same shape, and Python — like Java — handles the memory for you:

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt      # another Node, or None at the end

a = Node(10)
b = Node(20)
a.next = b                   # link a to b

Three languages, one idea. A node holds a value and a reference to the next node. The reference is Node* in C++ (a raw pointer you free yourself), Node in Java (a reference the GC tracks), and self.next in Python (an attribute that is another Node or None). The end of the list is marked by the absence of a next — nullptr, null, or None. The list itself is just a reference to the first node, the head. Follow next from the head and you walk the whole chain.

Coach’s Note — In C++ you could see that each new Node was a separate heap allocation at some address the OS chose — and the addresses were nowhere near each other. Java and Python hide the addresses, but the truth is unchanged: every node is its own little object somewhere on the heap, and “somewhere” means scattered. Hold that picture. It is the entire reason the linked list loses the cache battle in §3.5. The architect keeps the C++ memory model in their head even when the language hides it.

The defining contrast with the array, stated plainly:

The array trades flexibility for a tight, fast layout. The linked list trades the tight layout for never having to shift or resize. That trade is the whole chapter.

3.2 — The Singly Linked List: Prepend, the O(1) Star

A singly linked list is a chain of nodes where each node points only forward, to its successor. The list object holds a reference to the head (and, as we’ll see, optionally the tail).

Start with the operation that is the linked list’s reason for existing: prepend — insert at the front. This is where the list shines and the array bleeds.

class Node:
    __slots__ = ("value", "next")        # __slots__ saves memory; more in §3.5
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt


class SinglyLinkedList:
    def __init__(self):
        self._head = None
        self._length = 0

    def prepend(self, value):
        """Insert at the front. O(1) — no walk, no shift."""
        self._head = Node(value, self._head)   # new node points at old head...
        self._length += 1                       # ...and becomes the new head

Read prepend until it is obvious. A new node is created, its next is set to the current head, and then the head is moved to point at the new node. Three constant-time steps, no matter whether the list has zero elements or a billion. O(1), always. Compare that to list.insert(0, x), which shifts every existing element right one slot — O(n). For a workload that hammers the front, this is the linked list’s genuine, asymptotic, real win. Hold onto it; it is rarer than the textbooks imply.

Now append — insert at the back. Here is the first place the naive linked list is worse than you’d hope. With only a head pointer, finding the back means walking the entire list:

    def append_slow(self, value):
        """Insert at the back WITHOUT a tail pointer. O(n) — must walk to the end."""
        node = Node(value)
        if self._head is None:
            self._head = node
        else:
            cur = self._head
            while cur.next is not None:    # walk all the way to the last node
                cur = cur.next
            cur.next = node                # splice the new node onto the end
        self._length += 1

That while loop is O(n). Appending n elements this way is O(n²) — exactly the disaster we warned about in Chapter 2. The fix is a classic and worth internalizing: keep a tail pointer.

3.3 — The Tail Pointer: Making Append O(1)

A tail pointer is a second reference, held by the list, that always points at the last node. With it, append never walks — it splices directly onto the known end.

class SinglyLinkedList:
    def __init__(self):
        self._head = None
        self._tail = None        # always points at the last node (or None if empty)
        self._length = 0

    def prepend(self, value):
        """O(1). Insert at the front."""
        self._head = Node(value, self._head)
        if self._tail is None:           # the list was empty: head is also tail
            self._tail = self._head
        self._length += 1

    def append(self, value):
        """O(1) — BECAUSE of the tail pointer. No walk."""
        node = Node(value)
        if self._tail is None:           # empty list: head and tail both = node
            self._head = self._tail = node
        else:
            self._tail.next = node        # splice onto the old tail
            self._tail = node             # the new node is the new tail
        self._length += 1

The tail pointer costs you exactly one extra reference per list — not per node, per list. For that one-pointer price, append drops from O(n) to O(1). This is a perfect small example of the architect’s trade: a tiny, fixed memory cost buys an asymptotic speedup on a common operation. You will almost always want the tail pointer. The only bookkeeping it demands is discipline: every operation that could change the last node — append, and delete when it removes the tail — must keep _tail honest. Forget that and you get one of the nastiest linked-list bugs there is (see §3.8).

Coach’s Note — “Keep a pointer to the thing you’ll need fast” is one of the oldest moves in systems programming, and the tail pointer is your first taste of it in this book. You’ll see it again everywhere: a database keeps a pointer to the last page it wrote; a log keeps a pointer to the tail of the file; an LRU cache keeps pointers to both ends of a list. The pattern is always the same — pay a little fixed memory to turn an O(n) search into an O(1) lookup. Recognize it once and you’ll recognize it forever.

3.4 — Find, Delete, __iter__, and __len__

The rest of the singly linked list is walking. Find locates the first node holding a value — and there is no shortcut, because the list has no index arithmetic. You must follow next from the head until you find it or fall off the end. O(n).

    def find(self, value):
        """Return the first Node holding `value`, or None. O(n) — must walk."""
        node = self._head
        while node is not None:
            if node.value == value:
                return node
            node = node.next
        return None

Delete is the operation that exposes the asterisk on the famous “O(1) delete” claim. Unlinking a node — once you and its predecessor are standing on it — is genuinely O(1): you point the predecessor’s next past the doomed node and it’s gone. But in a singly linked list you can only reach a node by walking from the head, and to splice a node out you need its predecessor (the node before it), because that’s whose next you have to rewire. So delete-by-value is O(n): the walk dominates.

    def delete(self, value):
        """Delete the first node holding `value`. Return True if removed. O(n)."""
        prev = None
        node = self._head
        while node is not None:
            if node.value == value:
                if prev is None:               # deleting the head
                    self._head = node.next
                else:
                    prev.next = node.next       # splice the node out
                if node is self._tail:         # deleting the tail: fix it!
                    self._tail = prev
                self._length -= 1
                return True
            prev = node                         # remember the predecessor
            node = node.next
        return False

Notice the three cases delete must handle correctly: removing the head (move _head forward), removing the tail (move _tail back to prev), and removing a middle node (rewire prev.next). Getting all three right — and keeping _length honest — is the rep. Forgetting the tail case is the bug.

Finally, the two dunder methods that make your list feel like a real Python collection. __len__ makes len(mylist) work and must be O(1) (so you track _length as you go, never recount). __iter__ makes for v in mylist work, and it is the pointer-chase made visible:

    def __len__(self):
        return self._length                     # O(1): we maintained it

    def __iter__(self):
        node = self._head
        while node is not None:
            yield node.value                    # hand back one value at a time
            node = node.next                     # ...then chase the pointer

That __iter__ is a generator — yield hands back one value and pauses, resuming on the next loop. It is the cleanest possible expression of “walk the chain.” It is also, as the next section proves, the exact operation where the linked list’s scattered-memory layout costs you.

3.5 — The Doubly Linked List: Two Pointers, One Genuine Win

A doubly linked list gives each node a second pointer — prev, aimed backward at the predecessor — in addition to next. The list still tracks head and tail.

class DNode:
    __slots__ = ("value", "next", "prev")
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None

Why pay for a second pointer on every single node? Two reasons, one minor and one that is the whole point.

The minor reason: you can walk the list backward (__reversed__ becomes free) and you can get O(1) operations at both ends, which is exactly what a deque needs — the structure you’ll build next week.

The major reason — the one workload where a linked list genuinely, asymptotically, and in real wall-clock time beats the array — is this: delete a node you already hold a reference to, in O(1). In the singly linked list, delete was O(n) because you had to walk to find the predecessor. With a prev pointer, the node knows its own predecessor. No walk. You splice it out directly:

    def delete_node(self, node):
        """O(1). Delete a node you ALREADY HOLD — no search, no walk."""
        if node.prev is not None:
            node.prev.next = node.next      # predecessor skips over us
        else:
            self._head = node.next          # we were the head
        if node.next is not None:
            node.next.prev = node.prev      # successor points back past us
        else:
            self._tail = node.prev          # we were the tail
        node.prev = node.next = None        # defuse the stale pointers; help GC
        self._length -= 1

This is the linked list’s crown jewel, and the only operation in this whole chapter where it cleanly beats the dynamic array on both Big-O and the constant factor. The array’s delete-from-the-middle is O(n) no matter what — it must shift every element after the gap left one slot to close it. The doubly linked list, given a held reference, does it in four pointer assignments. O(1). You will measure this win in numbers in the project, and the gap is enormous — milliseconds versus seconds.

The price, paid honestly: one extra pointer per node. A singly linked node is value + one pointer; a doubly linked node is value + two pointers. On a 64-bit machine that’s an extra 8 bytes per node, plus the per-object overhead Python already charges (which is why we use __slots__ — it strips the per-instance __dict__ and shrinks each node substantially). For a million nodes, the second pointer alone is another 8 MB. The architect names that cost: the doubly linked list buys O(1) held-deletes and backward traversal with one extra pointer’s worth of memory on every node. Whether that trade is worth it depends entirely on whether your workload actually does held-deletes. Most don’t.

Coach’s Note — This is the single most important pattern to extract from the chapter: a linked list is the right tool when you hold references to the nodes themselves and splice them in O(1) — an LRU cache moving a node to the front, an OS scheduler yanking a process out of a run queue, an editor’s piece-table splicing text. The instant you have to find the node by value or by index first, the O(n) walk eats the O(1) splice and the array wins. The win lives entirely in already holding the node. Remember that and you’ll know, in one sentence, when to reach for this structure.

3.6 — The Footrace: Why the Array Usually Wins Anyway

Now we settle the cliffhanger. The textbook says “linked list: O(1) insert; array: O(n) insert.” So the linked list should win, right? Race them and find out. (This is exactly what benchmark.py in this chapter’s code/ folder does — run it. It races the linked list against array_front_insert.py, a complete dynamic array you’re given so the front-insert race has an array that can insert at the front — the one operation Project 2’s Normal tier didn’t ask you to build.)

Here is the central, honest, uncomfortable truth: for almost every workload, the array wins the wall-clock race even where its Big-O is equal or worse. The reason is the memory layout, and it comes straight from Chapter 2.

Recall §2.2: the CPU is far faster than RAM, so it fetches memory a whole cache line at a time (≈64 bytes) and bets you’ll want the neighbors. An array is contiguous, so walking it front-to-back wins that bet on nearly every read — one slow trip to RAM hands you a dozen-plus elements at once. A linked list is the opposite: every node is a separate heap allocation, scattered to wherever the allocator had room. Walking the list means jumping from one random heap address to the next, missing the cache line on almost every step. Same O(n). Wildly different constant factor — in compiled languages like the C++ you learned, the linked-list traversal can be several times slower purely from cache misses, before you count the cost of allocating all those separate node objects.

And there’s a second tax stacked on top, specific to building structures in Python or Java: allocation. The array does one big allocation (and a handful of doubling resizes). The linked list does one separate allocation per node — a million new/Node() calls for a million elements, each touching the allocator, each producing an object with its own header. That per-node allocation overhead is real and it is large.

Put concretely, here is the shape of what you will measure. (These are representative numbers from the chapter’s benchmark.py at n = 40,000 on a typical laptop; yours will differ in magnitude but not in direction — that’s the lesson.)

Read that table slowly, because every row teaches.

Random access is the array’s home turf and the list’s nightmare: the array computes the address and fetches (O(1)); the list has no index, so it walks from the head every single time (O(n) per access). Here the Big-O difference is real and the array wins by thousands of times.

Front insert is the linked list’s home turf — and notice it wins only because the Big-O gap is a whole factor of n (O(n) total vs the array’s O(n²)). When the asymptotic gap is genuinely a factor of n, asymptotics win, full stop, and no constant factor saves the loser. That’s the case the textbook is (correctly) describing.

Traverse is the subtle one, and the most honest. In a compiled language the array would win this clearly on cache locality. In CPython the result is roughly a tie — and you must understand why, because it’s a lesson about measurement. The interpreter overhead per element (bytecode dispatch, the boxing of every int into a heap object — recall §2.5) is so large that it masks the hardware cache effect. Both structures are already chasing pointers to boxed integers; Python’s own list is itself an array of pointers to scattered int objects, so the cache advantage that a C int[] would enjoy is mostly thrown away before the linked list even enters the picture. The cache penalty of the linked list is real and is in the predicted direction; it is simply swamped by a bigger constant. That nuance — “the effect is real but masked by a larger overhead at this layer” — is exactly the kind of thing an architect measures rather than assumes. Run it in C and the array pulls ahead on traversal; run it in CPython and it’s a wash. Both facts are true at their own layer.

Coach’s Note — “Linked lists are O(1) insert” is true and almost always irrelevant, because (a) you usually have to find the insertion point first, which is O(n) and erases the win, and (b) when you don’t, the array’s contiguity and Python’s fast C-level list operations beat the per-node allocation and pointer-chase anyway. The list wins exactly two situations: a genuine factor-of-n asymptotic gap (front-insert-heavy workloads with no search), and the O(1) held-node splice. Outside those two, reach for the array — which in Python means just use a list. Measure before you believe. That’s the whole discipline.

3.7 — The Cost Comparison Table (Memorize This)

Here is the master comparison — the linked-list row of the cost table you began in Chapter 2, set beside the dynamic array, with both the asymptotic cost and the real-world (cache / allocation) annotation. This table is the chapter.

The shape to carry in your head: the array is better at the ends and at random reads; the linked list is better only at the front (asymptotically) and at splicing nodes you already hold (genuinely). Everywhere else, the array’s contiguity and bulk allocation win the constant-factor war even when the asymptotics are tied. The linked list’s celebrated O(1) operations are real — they are just narrower than the legend.

3.8 — Common Bugs

The bugs that bite when you build linked lists — and they bite hard, because a single mis-set pointer corrupts the whole chain silently.

Bug: Forgetting to update the tail pointer on a delete that removes the last node. The list still “works” until you append again — then you append onto a node that’s no longer in the list, and elements vanish. Example: Deleting the tail without if node is self._tail: self._tail = prev. Next append splices onto the orphaned old tail; the new element is unreachable from the head. Fix: Every operation that can change the last node — delete of the tail, prepend/append on an empty list — must keep _tail consistent. Make “head, tail, and length are all honest after every operation” an invariant you check.

Bug: Losing the rest of the list by reassigning next in the wrong order during an insert. Example: node.next = self._head; self._head = node is correct. Reverse the two lines — self._head = node; node.next = self._head — and node.next now points at itself. The old list is leaked and you have a one-node infinite loop. Fix: When splicing, wire the new node’s pointer to the existing chain first, then move the head/tail. Draw the boxes and arrows on paper before you type. Order matters.

Bug: Off-by-one in __len__ because you incremented length on insert but forgot to decrement on delete (or vice versa). Example: delete returns True but never runs self._length -= 1; len(mylist) now over-reports forever. Fix: Treat _length as a strict invariant: every successful insert is +1, every successful delete is -1, no exceptions. Never recompute it by walking — that would make __len__ O(n).

Bug: Walking off the end because you checked node.value before checking node is not None. Example: while node.next.value != x: blows up with AttributeError: 'NoneType' object has no attribute 'value' the moment node.next is None. Fix: The loop guard is always while node is not None: — check existence before you dereference. This is the Python echo of the C++ null-pointer dereference and the Java NullPointerException. Same bug, three languages.

Bug: Creating a cycle by accident and turning __iter__ into an infinite loop. Example: A buggy delete sets prev.next = node (the doomed node) instead of prev.next = node.next, leaving a node pointing back into the chain. for v in mylist never terminates. Fix: After any operation that rewires pointers, sanity-check on small inputs that iteration terminates. In a debugger, a list that never ends printing is the signature of an accidental cycle.

Bug: Assuming delete_node is O(1) on a singly linked list. It isn’t — you need the predecessor, which requires a walk. Example: Writing a “fast O(1) delete” on a singly linked list and being surprised it’s slow. The O(1) held-delete needs the prev pointer; that’s why it lives on the doubly linked list. Fix: O(1) held-delete requires a doubly linked node (or that the caller hand you the predecessor too). On a singly linked list, deleting a held node is still O(n). Know which structure gives which guarantee.

3.9 — When a Linked List Is the Right Tool (and When It Isn’t)

The architect chooses. So let’s choose. Reach for a linked list when — and only when:

• You splice nodes you already hold, in O(1). An LRU cache moving a recently-used entry to the front; an OS scheduler pulling a process out of a run queue; a text editor’s piece table inserting a span. You hold the node, you splice in four pointer assignments, you never walk. This is the linked list’s true home.
• You insert/delete at the front (or both ends) constantly and never need random access. A queue or deque of unknown size built on a linked list never reallocates and never shifts. (Next week you’ll see the array-backed ring buffer often beats it anyway — but the linked-list deque is a legitimate, simple choice.)
• You need stable addresses — a reference to an element must stay valid even as the collection grows. An array’s resize moves every element to a new buffer, invalidating any raw pointer into the old one (you felt this in C++: a vector reallocation invalidates iterators). Linked-list nodes never move; a pointer to a node stays valid for the node’s life. When other code holds references into your structure, this matters.
• Elements are huge and copying dominates. When each element is a large object, the array’s shift-and-resize copies those big elements around; the linked list only ever moves pointers. If a copy is expensive and you do lots of middle insertion, the list’s pointer-only splices can win. (In Python, list elements are already pointers, so this matters far more in C++ than in Python — name the language when you make this call.)

Reach for an array (in Python, just a list) — which is almost everything — when:

• You need random access by index. O(1) vs O(n). Not close.
• You build-then-iterate, or append-and-read far more than you front-insert. The array’s bulk allocation and cache-kindness win.
• Memory is tight. The linked list pays a pointer (or two) of overhead per element, plus per-node object headers. The array’s overhead is one buffer and a little slack.
• You’re not sure. The default in Python is the list, and the default is right for the vast majority of programs, because most programs append, index, and iterate — exactly the array’s strengths.

Coach’s Note — Here is the sentence to walk out of this chapter with: the linked list is the right tool when you already hold references to the nodes and splice them in O(1), or when stable addresses matter; for nearly everything else, the contiguous array wins on the constant factor even where the Big-O is tied, so reach for the list. You earned that judgment by building both and racing them. That is the difference between a coder who recites “O(1) insert” and an architect who knows what it actually costs.

3.10 — Reps

Open the exercises for the full set. This week’s reps build the muscles the project demands: wiring nodes without leaking the chain, keeping head/tail/length honest, walking with __iter__, and measuring the footrace so the cost lesson is something you’ve felt, not something you’ve been told. AI stays OFF — Phase 1. You cannot reason about the cost of a structure you have never built and broken yourself.

A preview:

• Rep 1 — Build Node and a prepend-only list; print it; confirm O(1) front insert by reading the code.
• Rep 4 — Add the tail pointer and prove append went from O(n) to O(1) by inspection and timing.
• Rep 7 — Handle all three delete cases (head, tail, middle) and write the test that catches the tail-pointer bug.
• Rep 11 — Race traversal and random access against a Python list and explain the gap with §3.6.

Do every one. The reps are the conditioning; the project is the game.

3.11 — This Week’s Project

You’re ready for Project 3 — Linked List vs Array Benchmark, in Project 3.

You will implement a singly linked list by hand (Node, prepend, append, find, delete, __len__, __iter__), test it, and then write a benchmark harness that races it against your DynamicArray from Project 2 across four workloads: random access, front insertion, back insertion, and full traversal. The Medium tier adds a doubly linked list and the one workload the linked list genuinely wins — delete a node you already hold — shown in numbers. The Hard tier is an architectural memo: given your own measurements, name the specific, realistic workloads where you’d choose a linked list over a dynamic array and where you wouldn’t, citing your numbers and the place where cache locality made the asymptotically “worse” structure win.

Like every Phase 1 project, the code is half the grade and the honest accounting of what it cost is the other half. The memo is where you stop reciting Big-O and start deciding with it.

3.12 — Coach’s Final Word for Week 3

This week you built the structure that is the most literal answer in computer science to Paul’s question — how are many members joined into one body? Many separate nodes, each scattered somewhere on the heap, joined into one sequence by the pointers between them. You learned that a node is value plus a next pointer; that prepend is O(1) and append is O(1) if you keep a tail; that find and delete are O(n) because you must walk; that the doubly linked list buys O(1) held-deletes and backward traversal with one extra pointer per node.

And you learned the lesson that separates this chapter from the textbook version: the famous “O(1) insert” is true and usually loses anyway. Big-O describes how cost grows, not how much it is, and the linked list’s scattered nodes pointer-chase across cache lines and pay a per-node allocation tax that the array’s contiguity and bulk allocation simply don’t. The array — the Python list — wins most real workloads on the constant factor even when the asymptotics are tied. You didn’t take that on faith. You measured it.

If the cache argument still feels abstract: run benchmark.py, read the random-access and front-insert rows, and watch the constant factor become a wall-clock number. Close the gap by feeling it.

The body is one and has many members. The members are joined, and the joining has a cost — a pointer per link, a cache miss per step, an allocation per node. The architect names that cost and chooses anyway, with eyes open. That is the work.

See you on Monday.

Up next: Read the exercises and complete every rep. Then open Project 3 and race the structures with your own hands. After that, Chapter 4 — stacks, queues, and deques, where the same data can sit on an array or a linked list and the choice is a real tradeoff.

Previously: Chapter 2 — arrays and the memory you can feel, where we built the dynamic array and asked whether its O(n) middle could be beaten.