Arrays and Linked Lists: Cost Follows Access Pattern

An array stores elements in contiguous indexed positions. A linked list stores each value next to a pointer to the next one.

On paper the difference looks small. Arrays index in O(1) while lists need O(n) traversal. In memory the gap reaches two orders of magnitude. The two layouts ask completely different things of the cache.

This article compares them honestly. It covers indexing, insertion, memory overhead, and the access patterns that decide which one wins.

Indexing computes an address, traversal follows pointers

An array finds element i with arithmetic. It multiplies i by the element size and adds the base address. The hardware finishes in about one cycle.

A linked list has no such formula. A node holds one value plus a pointer to the next node. Reaching the i-th node means following i pointers in sequence.

Each pointer hop depends on the previous load. The processor cannot fetch the next address before the current one arrives. Prefetching cannot help. Parallel loading cannot help either.

The same program shape below runs in three languages. It reads the element at index 3 from both layouts:

#include <vector>
// Compare direct indexing with walking node by node.
// The vector version computes; the list version follows pointers.
struct Node { int value; Node* next; }; // one list node
int atIndex(Node* head, int i) {
    // Walk i links: each step waits for the previous load.
    Node* cur = head;
    for (int k = 0; k < i; k++) cur = cur->next;
    return cur->value; // arrived after i dependent hops
}
int demo() {
    std::vector<int> a = {10, 20, 30, 40}; // contiguous storage
    int fast = a[3]; // one multiply-add, then one load: 40
    Node n3{40, nullptr}, n2{30, &n3}, n1{20, &n2}, n0{10, &n1};
    int slow = atIndex(&n0, 3); // three hops to reach the same 40
    return fast + slow;
}

The array version costs one load. The list version costs i dependent loads. At roughly 100 nanoseconds per hop from main memory, a million-node walk takes about a tenth of a second. The equivalent array sweep finishes in a few milliseconds.

Insertion rewires cheaply but finds its place slowly

Lists win one narrow contest. Inserting at a known node takes three pointer writes. No elements move. The operation itself is O(1).

The catch is reaching that node. Finding position i still costs O(n) traversal. The cheap rewiring never includes the expensive walk.

Arrays pay the mirror cost. Inserting at position i shifts every later element one slot right. That shift costs O(n - i) moves. The moves run fast per element because they sweep cache lines, but there are many of them.

Appending at the end is the special case that saves arrays. A dynamic array doubles its capacity when full, so n appends copy O(n) elements total. Each append costs O(1) amortized, meaning averaged across the sequence. C++ vector doubles. CPython lists grow by a factor near 1.125 plus a few spare slots.

Memory overhead changes the math

A list node carries bookkeeping with every value. An integer plus a pointer on a 64-bit machine occupies 16 bytes: 4 for the value with padding, 8 for the pointer, plus allocator alignment.

The same integer in an array occupies exactly 4 bytes. The list therefore uses four times the memory for the same data. It also spends half of every cache line on pointers instead of values.

Allocator behavior widens the gap. Array elements arrive in one block with one allocation. List nodes often arrive from scattered allocations spread across the heap. Scattered nodes share few cache lines and defeat prefetching.

For ten million integers the array needs about 40 MB. The linked version needs about 160 MB plus allocator headers. The larger structure then runs slower precisely because it is larger.

Locality decides which layout wins

Big-O treats all O(n) scans as equal. Hardware disagrees. A contiguous scan of ten million integers moves about 40 MB across roughly 625,000 cache lines and finishes in a few milliseconds. Chasing ten million scattered nodes pays a dependent load per node and can take a hundred times longer.

The practical ranking for iteration-heavy work runs from contiguous arrays first, through block structures like arenas and B-trees, down to scattered linked nodes last.

Lists keep their place in narrow roles. An adjacency list built once and extended freely needs insert-anywhere structure without resizing. A queue with stable references across splices needs nodes that never move.

Circular buffers deserve a mention here. A ring over an array gives O(1) push and pop at both ends with full locality. It beats a linked queue in nearly every real implementation.

Where each layout wins and what to read next

Choose the layout that matches the access pattern. Scan and index often, and arrays win by prediction and density. Splice frequently at known positions with stable references, and lists earn their pointers.

Queues, deques, and growing buffers usually belong on arrays or rings. Graphs with unpredictable degree often store neighbor lists. Large tables that resize favor dynamic arrays with reserved capacity.

Watch the array and linked-list trace to see both layouts execute. Compare the memory layout diagram for the cache picture. Then study how indexing works for the address math behind O(1) access.