Foundations · Module 4
Linked lists
Nodes joined by pointers: cheap to rewire, expensive to walk.
A linked list trades the array's computed addresses for pointers: any node can be rewired in a couple of writes, but reaching a node means walking to it. This module builds lists from nodes, uses a dummy head to make insertion and deletion uniform, solves classic problems with fast and slow pointers, and then measures lists against arrays on real hardware, where the result surprises most people.
- 1Nodes and pointersA linked list is a chain of separately allocated nodes, each holding a value and the address of the next. Walking it is O(n), and rewiring it never moves a value.12 min
- 2Insert, delete and the dummy headInserting or deleting in a linked list is a couple of pointer writes, if you hold the node before the change. A dummy head node removes the special case of changing the first node.13 min
- 3Fast and slow pointersTwo pointers walking a list at different speeds find its middle, the node n from the end, and whether it loops back on itself, all in one pass with O(1) memory.14 min
- 4Arrays vs linked lists on real hardwareOn paper, linked lists win at inserting in the middle. On real hardware, arrays win almost every benchmark, because of cache lines, allocation and memory overhead. Here is why, and where lists still win.13 min