Linked list visualizer
A linked list stores each element in its own node with a pointer to the next one, so inserting is a matter of rewiring pointers rather than shifting elements. Run the same operations on a singly linked list, a doubly linked list and an array, and count what each one touches in memory.
Nodes allocated at different times end up anywhere in the heap: 6 elements, 6 different cache lines, and every next pointer is a jump to an unrelated address.
- –Each step of the operation is listed here as it runs.
How to use the simulator
Each box is an element with its value and the last digits of its memory address. Choose an operation and the steps play out: visited elements are shaded, and the side panel lists every pointer followed, pointer written and element moved. The strip below the list shows where the elements sit in memory.
- Add at the end of a singly linked list: with only a head pointer it walks the whole list first. A doubly linked list keeps a tail and does it in four pointer writes.
- Add at the front of the array: every element shifts one slot. The list just writes two pointers.
- Switch placement between side by side and scattered and watch the memory strip: the same list can use a few cache lines or one per node.
What is a linked list?
A linked list is a sequence whose elements are stored in separate nodes, each holding a value and a reference to the next node. The list itself is just a reference to the first node, the head; the last node points to nothing. A doubly linked list adds a reference to the previous node, so it can be walked both ways and a node can be unlinked knowing only itself; a circular list joins the last node back to the first.
The appeal is that changing the sequence never moves data: a new node is spliced in by changing two pointers, wherever it goes. The cost is that nothing can be found without walking from the head, and that the nodes are scattered in memory.
Operations and their cost
Steps taken on a sequence of 1,000 elements: elements read while walking, pointers written and elements moved. The singly linked list has only a head pointer, the doubly linked list a head and a tail, and the array has spare capacity:
| Operation | Singly linked | Doubly linked | Array |
|---|---|---|---|
| Add at the front | 2 ptr | 4 ptr | 1001 moved |
| Add at the end | 1000 read, 2 ptr | 4 ptr | 1 moved |
| Insert in the middle | 500 read, 2 ptr | 500 read, 4 ptr | 501 moved |
| Remove from the middle | 501 read, 1 ptr | 501 read, 2 ptr | 499 moved |
| Find the last value | 1000 read | 1000 read | 1000 read |
| Reverse | 1000 read, 1001 ptr | 1000 read, 2002 ptr | 1000 moved |
The list wins only where it does not have to walk: at the front, and at the end when it keeps a tail. Inserting in the middle costs a walk of half the list instead of a shift of half the array, and those are not equal costs: the shift is one sequential memory copy that hardware does very fast, while the walk is a chain of dependent loads, each of which has to finish before the next address is known. When a program already holds a reference to the node, as an LRU cache does through its hash map, the list's O(1) insert and delete are real.
Memory and the cache
Each node is its own heap allocation. With 64-bit glibc malloc, which adds 8 bytes of bookkeeping and rounds to 16 with a minimum of 32, a node holding one 8-byte value uses:
| Structure | Payload per element | Memory per element |
|---|---|---|
| Array | 8 B | 8 B |
| Singly linked | 16 B | 32 B |
| Doubly linked | 24 B | 32 B |
The bigger cost is locality. A processor reads memory in 64-byte cache lines, so an array of 8-byte values brings in eight elements per miss. List nodes allocated one after another are almost as good; nodes allocated at different times, as in any long-lived list, are spread across the heap. Cache lines missed per element when summing a list or array once, in a model of a 32 KiB, 8-way L1 data cache with no prefetching:
| Elements | Array | List, nodes side by side | List, nodes scattered |
|---|---|---|---|
| 1,000 | 0.125 | 0.500 | 0.997 |
| 10,000 | 0.125 | 0.500 | 0.996 |
| 100,000 | 0.125 | 0.500 | 0.996 |
A miss to main memory costs on the order of a hundred nanoseconds, against about a nanosecond for an L1 hit. Real processors also prefetch: they detect sequential access and load the next lines early, which helps arrays and side-by-side nodes, but they cannot prefetch a scattered list because the next address is only known once the current node has arrived. This is why linked lists are often slower than arrays even for the insertions they are supposed to be good at.
Two-pointer techniques
Many list problems are solved with two references moving at different speeds. To find the middle, advance one pointer by one node and another by two; when the fast one reaches the end, the slow one is in the middle, after one pass and without knowing the length. To find the k-th node from the end, start the second pointer k nodes ahead.
Floyd's cycle detection, the tortoise and the hare, uses the same idea to find a loop in O(1) memory: if the list has a cycle, the fast pointer eventually laps the slow one inside it. Restarting one pointer from the head and moving both one step at a time, they meet at the first node of the cycle. Steps taken by the model, which is checked against a search that records every visited node:
| Nodes | Tail points back to | Steps | Cycle starts at | Cycle length |
|---|---|---|---|---|
| 10 | 3 | 10 | 3 | 7 |
| 100 | 40 | 100 | 40 | 60 |
| 1,000 | 0 | 1,000 | 0 | 1000 |
| 1,000 | 999 | 1,998 | 999 | 1 |
Where linked lists are used
- Intrusive lists in kernels. The Linux kernel's
list_headis a circular doubly linked list whose links are embedded in the objects themselves, so an object can sit on several lists without extra allocations and be removed in O(1) from wherever it is. - LRU caches. A hash map finds the entry and a doubly linked list keeps the order of use; moving an entry to the front or dropping the oldest is a few pointer writes.
- Allocators. Free blocks are kept on free lists threaded through the free memory itself.
- Functional languages. Immutable singly linked lists let many versions share their tails, the basis of lists in Lisp, Haskell and Clojure.
- Skip lists stack several linked lists to get O(log n) search, and hash tables with separate chaining keep a short list per bucket.
History
Allen Newell, Cliff Shaw and Herbert Simon introduced linked lists in 1955 and 1956 as the main data structure of their Information Processing Language, working at the RAND Corporation and the Carnegie Institute of Technology on early artificial intelligence programs such as the Logic Theory Machine. Hans Peter Luhn had already suggested chaining entries in a hash table in an IBM memorandum in 1953. John McCarthy made the list the central data structure of Lisp, which he created in 1958 and described in his 1960 paper "Recursive functions of symbolic expressions and their computation by machine", built from cells of two pointers accessed with car and cdr. Robert Floyd's cycle-detection method is known through Donald Knuth, who attributes it to him in The Art of Computer Programming.
Linked list questions and answers
When should I use a linked list instead of an array?
When you insert or remove in the middle of a sequence through a reference you already hold, often enough that shifting elements would dominate: an LRU cache moving entries to the front, a scheduler’s run queue, an allocator’s free list. If you have to walk to the position first, the walk costs as much as the shift and touches far more memory: inserting in the middle of 1000 elements took 502 steps in a singly linked list and 501 element moves in an array, but the array’s moves are one contiguous copy.
Why are linked lists slow in practice?
Because each node is a separate allocation, and following a pointer to one that is not in cache costs a trip to memory. Summing 100,000 values in this page’s cache model misses on 0.125 cache lines per element for an array, 0.50 for a list whose nodes happen to sit next to each other, and 1.00 for a list spread over the heap: nearly every node is a miss. Hardware prefetchers also predict array walks easily and pointer chasing hardly at all.
What is the time complexity of linked list operations?
Inserting or removing at a node you already have is O(1): a couple of pointer writes. Reaching a position is O(n), since you must follow next pointers from the head. A singly linked list with only a head pointer needs O(n) to append; keeping a tail pointer, or using a doubly linked list, makes it O(1). Search is O(n) in both lists and arrays, but an array also gives O(1) access by index.
How do you detect a cycle in a linked list?
Floyd’s tortoise and hare: move one pointer one step and another two steps at a time; if there is a cycle they meet inside it, and then a pointer from the head and one from the meeting point, both moving one step, meet at the cycle’s start. It uses O(1) memory. For a 100-node list whose tail links back to node 40, the model finds the start (40) and length (60) in 100 steps.
How much memory does a linked list node use?
More than its contents. A node with one 8-byte value and one pointer is 16 bytes, but each node is a separate allocation, and 64-bit glibc malloc rounds that up to a 32-byte chunk. A doubly linked node (24 bytes) also takes 32. An array stores the same value in 8 bytes, plus up to half its capacity unused after it grows.
How do you reverse a linked list?
Walk the list once with three references, previous, current and next: save current.next, point current.next at previous, then advance previous and current. When current reaches null, previous is the new head. It takes one pass and one pointer write per node, with no extra memory.
Further reading
- Linux kernel sourceinclude/linux/list.hThe circular doubly linked list used throughout the kernel.
- McCarthy, Communications of the ACM, 1960Recursive functions of symbolic expressions and their computation by machine, Part ILisp, and lists built from two-pointer cells.
- GNU C Library sourcemalloc/malloc.cChunk sizes and overhead, and the free lists the allocator keeps.
- Ulrich Drepper, 2007What Every Programmer Should Know About MemoryCaches, prefetching and the cost of following pointers, with measurements of list traversals.