Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture V of XIV

Lecture V · Data Structures & Algorithms

Linked lists and the wrapper pattern

Last lecture ended on a sore point: a Python list makes a fine stack but a miserable queue, because pop(0) has to slide every remaining element one slot to the left. That shifting is not a bug in Python’s list; it is the price of the thing that makes a list fast everywhere else. So this lecture takes the pain seriously and builds the structure that does not have it.

The cost of contiguous memory

A Python list is a block of slots laid end to end in memory. That layout is why xs[i] is instant: the machine knows where slot 0 lives and how wide a slot is, so it multiplies and jumps straight there, no matter how big the list is. Random access, O(1)O(1), is the whole reason arrays earn their keep.

The bill comes due at the front. To insert at index 0, every existing element has to move up one slot to make room, because the slots are physically adjacent and there is nowhere else for the new value to go. Delete from the front and the same crowd shuffles back down. On a list of a million items, one insert(0, x) or pop(0) is a million moves. That is the O(n)O(n) we watched turn a list-backed queue quadratic.

So here is the trade we are about to make. We give up the contiguous block, and with it instant indexing, in exchange for a structure where adding and removing at the ends, and splicing in the middle, cost the same tiny amount every time. Nothing is free; we are buying cheap edits by selling fast lookups. Whether that is a good deal depends entirely on what you are going to do with the thing, which is the recurring question of this whole course.

A node, and the smallest list that works

If the elements are not going to sit next to each other, then each one has to carry directions to the next. That is the entire idea of a linked list. The unit is a node: a little object holding one piece of data and a reference to the node that follows it.

class Node:
    def __init__(self, data, nxt=None):
        self.data = data
        self.next = nxt

A chain is just nodes holding each other’s hands. If I keep a reference to the first node, I can reach the rest by following next until I fall off the end at None. Notice what this buys me: to put a new item on the front, I do not move anything. I make one node whose next points at the current first node, and now that new node is the front.

class LinkedList:
    def __init__(self):
        self._head = None

    def add_first(self, data):
        self._head = Node(data, self._head)

    def remove_first(self):
        data = self._head.data
        self._head = self._head.next
        return data

Read add_first slowly, because it is the payoff. Node(data, self._head) builds a node whose next is the old head, and then self._head is rebound to that new node. Two references move. It does not matter whether the list held zero items or a billion; the work is identical. That is O(1)O(1), and it is exactly the front operation a Python list charges O(n)O(n) for. remove_first is the mirror image: read the head’s data, step _head forward one link, done.

python runs in your browser · first run downloads ~240 kb
Plate I A chain by hand. Three nodes wired tail-first, drawn by visualize as boxes with next arrows, then a fourth put on the front. Press Run. Only one link changes; nothing else moves, which is why add_first is O(1)O(1).

The wrapper pattern

The LinkedList class above already does something quietly important: it hides the nodes. A user of the list calls add_first and remove_first; they never touch a .next themselves. That separation is worth naming, because it is the lecture’s real lesson. The class wraps the raw nodes, and because it is the only thing that ever handles them, it can enforce invariants the bare nodes cannot.

Here is the first invariant that pays for itself. How long is a linked list? With only a head reference, the honest answer is “walk it and count,” which is O(n)O(n) every single time someone asks. That is absurd for a question as basic as length. So the wrapper stores the length in a field and adjusts it by one on every add and remove:

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

    def __len__(self):
        return self._length

    def add_first(self, data):
        self._head = Node(data, self._head)
        self._length += 1

    def remove_first(self):
        data = self._head.data
        self._head = self._head.next
        self._length -= 1
        return data

Now len(mylist) is O(1)O(1). This only works because the nodes are sealed behind the wrapper: if a user could splice in a node directly, the count would drift out of sync and the field would lie. The wrapper is what makes the stored length trustworthy, and that is the pattern, a class that owns its internals so it can promise things about them.

The same move buys us the other end. Keep a second reference, _tail, pointing at the last node, and suddenly appending to the back is O(1)O(1) too: make a node, point the old tail’s next at it, move _tail forward. Without a tail reference you would have to walk the entire list to find the end, O(n)O(n), every append. One stored pointer converts a linear operation into a constant one. A wrapper that holds _head, _tail, and _length can do add-front, add-back, remove-front, and length all in O(1)O(1). Hold onto the tail reference in particular, because it is about to do something even better.

Doubly linked, and concatenation for free

There is one thing the singly linked list still cannot do cheaply: go backwards. Each node knows its successor and nothing about its predecessor, so to delete a node you must know the one before it, which in general means walking from the head to find it. The fix is to make every node carry two references instead of one, prev as well as next. That is a doubly linked list, and it makes the interior cheap: given a node, you can splice it out by reaching both neighbours directly, because it is holding their addresses.

The tail reference plus the two-way links unlock the marquee trick. To concatenate list B onto the end of list A, you do not walk anything and you do not copy a single node. You reach straight to A’s tail, wire it to B’s head, wire B’s head back to A’s tail, and then update A’s tail to be B’s tail. Three assignments. It costs the same whether the lists hold two nodes each or two million, because you only ever touch the seam. That is O(1)O(1) concatenation, and it is the sort of thing a contiguous array simply cannot offer.

The plate below is a workbench for exactly these moves. Splice two lists in constant time and watch the three assignments land one at a time; delete an interior node and see its two neighbours join hands over the gap; then cut a single next pointer and watch half the list go dark, because a node nothing points into is a node you can no longer reach.

∅∅∅∅1head23tail4head5tail

Two doubly linked lists, A = 1·2·3 and B = 4·5. Each node keeps a next (top) and a prev (bottom); ∅ marks a null end. With scripting on, splice them into one in three assignments.

Plate II Pointer surgery. Doubly linked nodes with next arrows above and prev below; ∅ marks a null end. Press Splice, then Step: the ochre pointer is the one being changed this instant, green edges are settled, dashed grey nodes are orphaned. Try Delete node 2, then Cut after node 1 to strand the tail half. Play runs a whole operation; reduced-motion jumps to the finished wiring.

The cut is the one to sit with. When you null node1.next, node 2 still remembers node 1 through its own prev pointer, so the back-link looks intact. But reachability runs forward from the head, and nothing points into node 2 any more, so the entire tail half is lost the instant that one forward link is gone. This is the reason the wrapper guards its pointers so jealously: a single stray assignment to a next field can silently orphan an arbitrary amount of your data, with no error and no crash, just quietly unreachable memory. Interior deletion is O(1)O(1) and beautiful when you own the node; it is a footgun when you do not.

Plate II animates the surgery; now run it yourself on real objects. The workbench below builds two chains and joins them with a single assignment at the seam, then draws A before and after so you can count exactly what moved.

python runs in your browser · first run downloads ~240 kb
Plate III Splice by hand. build wires two chains; tail_of walks to A's end and one assignment hangs B off it. Press Run and compare the before and after snapshots: every original node is untouched, only the seam is new. The walk to the tail is the only cost this bare demo pays for not storing _tail.

What it costs

Nothing here is magic, and the honest accounting matters as much as the tricks. A linked list is very good at some things and genuinely bad at others, and the table is the point, not a footnote.

OperationPython list (array)Linked list (with tail + length)
Index xs[i]O(1)O(1)O(n)O(n), walk from the head
Add / remove at frontO(n)O(n), shift everythingO(1)O(1)
Add / remove at backO(1)O(1) amortisedO(1)O(1)
Insert / delete given the nodeO(n)O(n), shiftO(1)O(1), relink
LengthO(1)O(1)O(1)O(1), because we stored it
Search for a valueO(n)O(n)O(n)O(n)
Concatenate two listsO(n)O(n), copyO(1)O(1), splice the seam
Memory per elementone slota slot plus one or two references

Read the two columns as opposites, not as a winner and a loser. The array trades cheap edits for instant indexing; the linked list trades instant indexing for cheap edits at the ends and, once it is doubly linked, cheap edits anywhere you already hold the node. Search is a wash: both walk, both O(n)O(n). And the linked list is not free even where it wins, because every element now drags a node object and one or two extra references behind it, so it eats more memory than a tight array of the same values.

That is the shape of every choice in this course. There is no universally best container, only the right one for the operations you are actually going to perform. If you index constantly, keep the array. If you splice and shuffle the ends, reach for the links. Knowing which is which, and being able to say why in terms of a table like this one, is the skill the whole course is quietly training.

When the chain eats its tail

Every traversal we have written trusts one quiet promise: follow next far enough and you land on None. That promise is the wrapper’s job to keep, and it is one stray assignment away from a lie. Point some node’s next back at a node you already passed and the chain stops being a chain. It becomes a ring, and a ring has no None to fall off. The loop while cur is not None will circle forever, because the exit it is waiting for never comes.

This is the same reachability idea from the cut, seen from the other side. There a forward link went missing and stranded the tail; here a forward link points the wrong way and traps the walker. Both are the price of holding raw pointers: the structure will faithfully do exactly what your assignments say, including the things you did not mean.

python runs in your browser · first run downloads ~240 kb
Plate IV A chain, then a ring. Build 1 -> 2 -> 3, draw it ending at ∅, then set the tail's next back to the head and draw again: visualize marks the loop with ↩ cycle instead of a null end. The printed hops 1, 2, 3, 1, 2, 3, 1 show why a None-trusting traversal never terminates.

So how would you even notice a cycle without hanging the program? The classic trick needs no extra memory: run two walkers from the head, a slow one stepping one node at a time and a fast one stepping two. On a chain that ends at None, the fast walker simply falls off first and you are done. On a ring there is no edge to fall off, so the fast walker keeps lapping the slow one and eventually lands on the very same node: two pointers meeting is the tell that the list has swallowed its own tail. That is Floyd’s tortoise and hare, and it is worth knowing that a cycle is detectable at all, in one pass and constant space, the moment you stop trusting None blindly.

Problems

Work these in order. The last one runs its own checks; make every row green.

  1. Warm-up. On paper, draw a three-node singly linked list holding 10, 20, 30, with _head pointing at the first node. Now perform add_first(5) by drawing exactly the arrows that change. How many arrows moved, and did any existing node’s data change?

  2. Why the tail reference earns its keep. In one or two sentences, explain what append costs on a singly linked list that stores only _head, and what it costs once you also store _tail. Then say why you cannot keep a correct _tail unless the wrapper is the only thing allowed to touch the nodes.

  3. The orphan. Using Plate II, run Cut after node 1. Node 2’s prev pointer still aims at node 1, yet node 2 is unreachable. Explain, in terms of how reachability is computed, why a surviving back-pointer does not save it.

  4. The ring. Using Plate IV, build the three-node chain, then set the tail’s next back to the head. In one or two sentences, explain why the loop while cur is not None: cur = cur.next terminates on the chain but never on the ring. Then, without writing code, describe how two walkers moving at different speeds would let you detect the ring in a single pass.

  5. The main event. Finish add_first and remove_first so the wrapper keeps its promises: items stack at the head, the stored length stays exact, and draining the list leaves it empty. The starter gives you Node, the fields, __len__, and to_list; fill in the two stubs. Press Run to grade against the checks.

    The checks · run against your code

    # add_first stacks items at the head
    L = LinkedList()
    L.add_first(1); L.add_first(2); L.add_first(3)
    assert L.to_list() == [3, 2, 1]
    # length is stored, not recounted
    assert len(L) == 3
    # remove_first returns the head's data and shrinks the list
    assert L.remove_first() == 3
    assert L.to_list() == [2, 1]
    assert len(L) == 2
    # draining the list leaves it empty and length zero
    L.remove_first(); L.remove_first()
    assert L.to_list() == []
    assert len(L) == 0
    python runs in your browser · first run downloads ~240 kb
    Plate V The wrapper's contract. add_first and remove_first are stubbed; your job is to move the head reference and keep _length honest. Run grades the checks; Trace lets you step the head pointer node by node if a row stays red.
    Hint one

    add_first is one line of surgery plus one line of bookkeeping: rebind self._head to a new Node(data, self._head), then bump self._length. The old head becomes the new node’s next automatically.

    Hint two

    remove_first must read the data before it moves the head. Save self._head.data, step self._head to self._head.next, subtract one from _length, and return the saved value.

    The solution

    Each method is two moves, one to the links and one to the count:

    def add_first(self, data):
      self._head = Node(data, self._head)
      self._length += 1
    
    def remove_first(self):
      data = self._head.data
      self._head = self._head.next
      self._length -= 1
      return data

    Both are O(1)O(1): no walk, no shift, just a couple of references rebound. The stored _length stays exact only because these two methods are the sole gateway to the nodes, which is the wrapper pattern doing its job. A production list would also guard the empty case in remove_first, raising a clear error instead of letting the None head blow up, exactly the kind of contract we drew up when we studied ADTs.

  6. The other end, in constant time. Now that the wrapper stores _tail, appending to the back should cost the same whether the list holds two nodes or two million. Implement add_last so it wires a new node onto the tail and moves _tail forward, all in O(1)O(1), and handles the empty list where there is no tail to wire onto yet. The starter gives you the fields, __len__, and to_list; fill in the one stub. Run to grade against the checks.

    The checks · run against your code

    # add_last keeps items in the order they arrived
    L = LinkedList()
    L.add_last(1); L.add_last(2); L.add_last(3)
    assert L.to_list() == [1, 2, 3]
    # the stored length stays exact, no walk needed
    assert len(L) == 3
    # _tail points at the genuine last node
    assert L._tail.data == 3
    # and that last node really ends the chain
    assert L._tail.next is None
    # appending onto an empty list wires head and tail to one node
    M = LinkedList()
    M.add_last(99)
    assert M.to_list() == [99]
    assert M._head is M._tail
    assert len(M) == 1
    python runs in your browser · first run downloads ~240 kb
    Plate VI The O(1) back door. add_last is stubbed; use the stored _tail so no walk is ever needed. The checks probe the empty case, where head and tail become the same node, and the invariant that _tail.next stays None. Trace the append if a row stays red.
    Hint one

    Two shapes to handle. If self._head is None the list is empty, so the new node becomes both the head and the tail at once. Otherwise, hang it off the current tail with self._tail.next = node, then advance self._tail to that new node.

    Hint two

    Notice what you never do: walk. You never touch self._head in the non-empty branch, and you never loop to find the end, because self._tail already holds it. That absence of a walk is the whole point; it is what makes this O(1)O(1). Do not forget to bump self._length in both branches.

    The solution

    One node, one branch on emptiness, one bump of the count:

    def add_last(self, data):
      node = Node(data)
      if self._head is None:
          self._head = node
          self._tail = node
      else:
          self._tail.next = node
          self._tail = node
      self._length += 1

    The empty case is the one people drop: with no tail yet there is no next to reassign, so the new node has to seed both ends at once. After that, every append is the same short move, and it stays O(1)O(1) only because the wrapper faithfully keeps _tail aimed at the real last node. Let one outside caller splice past the wrapper and that promise, like the stored length before it, quietly stops being true.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.