Linked Lists

A linked list stores each element in its own node, with a pointer to the next node. Inserting or removing at a node you already hold is two pointer writes, and nothing else moves. Textbooks sell the structure on that property.

On real hardware the story has a second half. Getting to the node costs one pointer hop per element, and each hop is a likely cache miss (Chapter 4). The array usually wins even at the job the linked list was designed for, except in the few places where the program already holds the node. Those places turn out to be some of the most important code in any system.

Nodes and Pointers

Each element sits in a separately allocated node (Chapter 4) with a pointer to the next one. A doubly linked node adds a pointer to the previous one, which lets the list be walked backwards and lets a node be removed without finding its predecessor first. Inserting or deleting at a node you hold is O(1). Reaching position i from the head is O(i), one hop at a time.

Every node also carries overhead. On top of the element itself there are one or two 8-byte pointers and the allocator's own header, and in Python the node is a full object: a minimal node class with two fields takes 48 bytes on CPython 3.15, before counting the value it holds.

The Price of a Hop

The address of the next node is stored inside the current node. The processor cannot start fetching node k plus one until node k has arrived, and the prefetcher has no steady stride to follow (Chapter 4). So the misses happen one after another, never overlapped. A million-node traversal in which every hop misses the cache waits about a million times 100 nanoseconds, about 100 milliseconds. A million 8-byte values in an array stream through in about a millisecond.

Python shows the same shape. On CPython 3.15, walking a million nodes linked in the order they were allocated took 32 milliseconds. Linking the very same nodes in random order, so that each hop lands somewhere unpredictable, made the walk take 156 milliseconds, about five times longer. Summing a list of a million integers took 3.2 milliseconds.

Insert in the Middle, Search Included

To insert at a position, you first have to find it. The linked list walks there hop by hop, paying the ladder at every step. The array finds the position by index or by binary search (Chapter 7), then shifts its tail with one block move that the hardware performs at full bandwidth.

For "find the place, then insert", the array wins at the sizes people usually test, often by a wide margin. Bjarne Stroustrup, the designer of C++, made the result famous in a 2012 keynote by timing vectors, C++'s dynamic arrays, against linked lists on this task: the vector won across the sizes he showed, because the search dominates and the search is where the list is slowest.

Where Linked Lists Win

A linked list wins when the program already holds the node. The classic case is a least-recently-used cache. It keeps a hash table (see Hash Tables) from each key to that key's node, and a doubly linked list of the nodes in order of last use. A hit finds the node through the table, unlinks it and relinks it at the head, all in O(1). Eviction removes the node at the tail, also O(1).

CPython's own least-recently-used cache decorator and its ordered dictionary are both built this way in C, and allocators thread their free blocks into lists (Chapter 4). The other property that matters is stability: a node never moves, so a pointer to it stays valid for the node's whole life. An array cannot promise that, because growing it moves every element.

Intrusive Lists in Kernels

The Linux kernel embeds the link fields inside the objects themselves instead of wrapping each object in a separate node. One object can then sit on several lists at once, a process on the list of all processes and on its parent's list of children for example, with no extra allocation, and it can be removed from any of them in O(1).

The objects exist anyway, so the usual price of a separate node disappears. That is why kernels use linked lists heavily, in places where application code should not: the kernel always holds the node, and it never has to search the list to find it.

Linked Lists in a Python Service

In Python, a hand-written linked list pays for an object per node, dozens of bytes, and an interpreted step per hop (Chapter 13). It loses to the built-in list and to the deque almost every time. The linked lists worth having in a Python service are the ones already inside the ordered dictionary, the least-recently-used cache and the deque.

The memory bill is as lopsided. On CPython 3.15, a minimal node object takes 48 bytes, so a million nodes cost 48 megabytes before counting the values they hold, where a list of the same million values needs 8 megabytes of pointers. The nodes are also scattered wherever the allocator put them, which is the price of a hop all over again.

Writing a new one is justified by one thing only: an O(1) removal or move of a node you already hold, which nothing in the standard library provides for your case. Anywhere else, the cost is memory and cache misses for a benefit the program never uses.