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, , 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 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 , and it is exactly the
front operation a Python list charges for. remove_first is the mirror
image: read the head’s data, step _head forward one link, done.
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 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 . 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 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, , 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 . 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 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.
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.
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 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.
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.
| Operation | Python list (array) | Linked list (with tail + length) |
|---|---|---|
Index xs[i] | , walk from the head | |
| Add / remove at front | , shift everything | |
| Add / remove at back | amortised | |
| Insert / delete given the node | , shift | , relink |
| Length | , because we stored it | |
| Search for a value | ||
| Concatenate two lists | , copy | , splice the seam |
| Memory per element | one slot | a 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 . 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.
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.
Warm-up. On paper, draw a three-node singly linked list holding
10, 20, 30, with_headpointing at the first node. Now performadd_first(5)by drawing exactly the arrows that change. How many arrows moved, and did any existing node’sdatachange?Why the tail reference earns its keep. In one or two sentences, explain what
appendcosts 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_tailunless the wrapper is the only thing allowed to touch the nodes.The orphan. Using Plate II, run Cut after node 1. Node 2’s
prevpointer 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.The ring. Using Plate IV, build the three-node chain, then set the tail’s
nextback to the head. In one or two sentences, explain why the loopwhile cur is not None: cur = cur.nextterminates 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.The main event. Finish
add_firstandremove_firstso 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 youNode, the fields,__len__, andto_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 kbPlate 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_firstis one line of surgery plus one line of bookkeeping: rebindself._headto a newNode(data, self._head), then bumpself._length. The old head becomes the new node’snextautomatically.Hint two
remove_firstmust read the data before it moves the head. Saveself._head.data, stepself._headtoself._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 dataBoth are : no walk, no shift, just a couple of references rebound. The stored
_lengthstays 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 inremove_first, raising a clear error instead of letting theNonehead blow up, exactly the kind of contract we drew up when we studied ADTs.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. Implementadd_lastso it wires a new node onto the tail and moves_tailforward, all in , and handles the empty list where there is no tail to wire onto yet. The starter gives you the fields,__len__, andto_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 kbPlate 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 Nonethe list is empty, so the new node becomes both the head and the tail at once. Otherwise, hang it off the current tail withself._tail.next = node, then advanceself._tailto that new node.Hint two
Notice what you never do: walk. You never touch
self._headin the non-empty branch, and you never loop to find the end, becauseself._tailalready holds it. That absence of a walk is the whole point; it is what makes this . Do not forget to bumpself._lengthin 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 += 1The empty case is the one people drop: with no tail yet there is no
nextto reassign, so the new node has to seed both ends at once. After that, every append is the same short move, and it stays only because the wrapper faithfully keeps_tailaimed 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.