The idea: one block or a chain of nodes
An array stores its elements in one contiguous block of
memory. A linked list stores each element in its own node,
somewhere on the heap, and each node holds a next pointer to the following one. Both
hold the same sequence, but they pay for different operations.
On the canvas both structures start with 12 7 30 18 25 9. Every operation runs on the
array first, then on the list, and each panel counts steps (array: cells read,
written or moved; list: nodes visited or created) and cache misses.
Reading index i
Element i of an array is at base + 8·i (8-byte elements). The address is
computed, so the read is one step whatever i is: O(1). The list has no address formula: it
starts at head and follows i next pointers, O(i)
(Demo: read index 4: 1 step against 5).
Inserting and deleting
To insert at index i, the array must first make room by moving every later element one cell
right, starting from the end; deleting closes the gap by moving them left. At the front that is all
n elements (Demo: insert at the front: 7 steps). The list just writes two pointers:
new.next = head; head = new, one step (Demo: delete the front is the same in
reverse).
But the list's O(1) insert assumes you already hold the node before the spot. To insert at index 3 it first walks 3 nodes, so in the middle both are O(n): the array shifts what comes after, the list walks what comes before (Demo: insert in the middle: 4 steps each).
Growing a full array
An array block cannot be extended in place, because the memory after it may belong to something
else. A dynamic array (Java ArrayList, C++ std::vector, Python
list) allocates a bigger block, copies every element and frees the old one. The page grows
like ArrayList: capacity 8 becomes 8 + 8/2 = 12. That one append costs O(n),
but it buys room for many cheap appends, so appends are O(1) amortized
(Demo: append until the array grows: 1, 1, then 9 steps). The list with a
tail pointer appends in O(1) every time. See Dynamic
Array for the growth policy in detail.
Cache lines: why scanning an array is faster
The CPU does not fetch single bytes from memory: it loads a whole cache line, 64 bytes on today's x86 and ARM chips. A line holds 8 array elements, so reading one cell brings its 7 neighbours along for free. List nodes live at unrelated addresses, so every node is a new line. The canvas tints a loaded line blue and assumes the cache is empty at the start of each operation.
Both scans are O(n) steps, yet the array needs 2 misses for 6 elements and the list needs 6 (Demo: scan all). A miss to main memory costs roughly 100 times a cached read, and the hardware prefetcher can also guess the array's next line but not the list's next pointer. This is why arrays usually win even where Big-O says "same". See CPU Cache.
The costs
| operation | array | singly linked list |
|---|---|---|
| read / write index i | O(1) | O(i) |
| insert / delete at the front | O(n) shifts | O(1) |
| insert / delete at i | O(n − i) shifts | O(i) walk, then O(1) |
| append | O(1) amortized, O(n) when it grows | O(1) with a tail pointer |
| delete the last | O(1) | O(n): needs the node before it |
| scan | O(n), 1 miss per 8 elements | O(n), 1 miss per node |
| extra memory | unused capacity | one pointer per node + allocator overhead |
Which one to pick
Use an array by default: indexing, scanning, sorting and binary search all want contiguous memory. Use a linked list when you splice at nodes you already hold: an LRU cache moves a hit node to the front in O(1), allocators keep free lists, and the Linux kernel links objects that sit in several lists at once. The list operations themselves are animated on Linked List, and how arrays sit in memory on Arrays in Memory.
What the page leaves out
Doubly linked lists (O(1) delete of a held node and of the tail), circular buffers and deques, unrolled lists that store several elements per node, real allocator behaviour (nodes allocated together may in fact be close), prefetching, and cache sizes and eviction: the cache is simply empty at the start of each operation.
See where this page fits on the Basics mind map.