Why Arrays Are Faster Than Linked Lists (It Starts with the CPU Cache!)

The Benchmark That Confused Me

Early in my CS journey, a professor posed a question: "If both arrays and linked lists have O(n) traversal complexity, why does iterating an array of 10 million integers take ~10ms while iterating a linked list of the same size takes ~120ms on the same machine?"

The Big-O notation said they should be equivalent. The stopwatch disagreed — by 12x.

The answer lies not in the algorithm, but in the hardware running it. Specifically, in CPU caches.

---

The CPU Memory Hierarchy

Your CPU doesn't read directly from RAM every time it needs data. RAM is slow — accessing it takes ~100 nanoseconds, which at a 3 GHz clock speed is roughly 300 clock cycles of waiting. That's an eternity.

To compensate, CPUs have a hierarchy of smaller, faster caches:

        ┌─────────────────────────────────────────┐
        │              CPU Core                   │
        │  ┌─────────────┐  ┌─────────────┐       │
        │  │  Registers  │  │   L1 Cache  │       │
        │  │  ~0.3 ns    │  │  ~1 ns      │       │
        │  │  ~100 bytes │  │  32–64 KB   │       │
        │  └─────────────┘  └─────────────┘       │
        │                   ┌─────────────┐       │
        │                   │   L2 Cache  │       │
        │                   │  ~4 ns      │       │
        │                   │  256 KB–1MB │       │
        └───────────────────┴─────────────┘
                            ┌─────────────┐
                            │   L3 Cache  │
                            │  ~40 ns     │
                            │  8–32 MB    │
                            └─────────────┘
                            ┌─────────────┐
                            │     RAM     │
                            │  ~100 ns    │
                            │  8–64 GB    │
                            └─────────────┘

Each level is faster but smaller. The CPU always looks in L1 first, then L2, L3, and finally RAM.

---

Cache Lines: The Key Concept

Here's the critical insight: CPUs don't load one byte from memory — they load a full cache line.

A cache line is typically 64 bytes. When you access array[0], the CPU doesn't just fetch 8 bytes (one int64). It fetches the entire 64-byte block containing array[0] — which includes array[1] through array[7] as well.

Memory Layout of an Array:
┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
│ 0  │ 1  │ 2  │ 3  │ 4  │ 5  │ 6  │ 7  │ 8  │ 9  │
└────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
 ◄────────── 64-byte cache line ──────────►
 Access [0] → CPU loads [0..7] into L1 cache
 Access [1] → Already in L1 cache! (cache HIT)
 Access [2] → Already in L1 cache! (cache HIT)
 ...
 Access [7] → Already in L1 cache! (cache HIT)
 Access [8] → Loads next cache line [8..15]

For an array, this is wonderful. You read one element, and the next 7 come along for free, already sitting in L1 cache. This is called spatial locality.

---

Why Linked Lists Break This

A linked list node looks like this in memory:

type Node struct {
    Value int      // 8 bytes
    Next  *Node    // 8 bytes — a pointer to somewhere in memory
}

Each node is a separate heap allocation. The allocator places them wherever free memory is available. After thousands of allocations and frees, a linked list's nodes are scattered across memory:

Memory (scattered):
Address 0x0010: Node{Value: 42,  Next: → 0x7F40}
Address 0x0040: Node{Value: 17,  Next: → 0x0010}  ← something else
...
Address 0x7F40: Node{Value: 99,  Next: → 0x0200}
...
Address 0x0200: Node{Value: 5,   Next: → nil}

Traversal in Go:

// Array traversal — sequential memory
for i := 0; i < n; i++ {
    sum += arr[i]  // Cache HIT after first load
}

// Linked list traversal — pointer chasing
for node != nil {
sum += node.Value
node = node.Next  // Cache MISS — pointer goes to random address
}

Every node = node.Next dereferences a pointer to a random memory location. The CPU can't predict where the next node will be, so it can't prefetch it. This is called a cache miss — the CPU must stall and wait for RAM to respond (~100ns per miss).

---

A Real Benchmark

Here's a simple Go benchmark that demonstrates the difference:

package main

import (
"fmt"
"time"
)

const N = 10_000_000

type Node struct {
value int
next  *Node
}

func sumArray(arr []int) int {
sum := 0
for _, v := range arr {
sum += v
}
return sum
}

func sumLinkedList(head *Node) int {
sum := 0
for n := head; n != nil; n = n.next {
sum += n.value
}
return sum
}

func main() {
// Build array
arr := make([]int, N)
for i := range arr {
arr[i] = i
}

// Build linked list
head := &Node{value: 0}
cur := head
for i := 1; i < N; i++ {
cur.next = &Node{value: i}
cur = cur.next
}

// Benchmark array
start := time.Now()
_ = sumArray(arr)
fmt.Printf("Array:       %v\n", time.Since(start))

// Benchmark linked list
start = time.Now()
_ = sumLinkedList(head)
fmt.Printf("Linked List: %v\n", time.Since(start))
}

Typical output on a modern machine:

Array:       8.2ms
Linked List: 98.7ms

12x difference — matching what my professor described.

---

When Should You Use Each?

This doesn't mean linked lists are useless. They shine when:

Operation	Array	Linked List
Sequential read	Fast (cache-friendly)	Slow (pointer chasing)
Random access by index	O(1), fast	O(n), slow
Insert/delete at middle	O(n) — shift elements	O(1) — update pointers
Insert/delete at head	O(n)	O(1)
Memory overhead	Low (contiguous)	High (pointers + fragmentation)

A linked list is the right choice when you have frequent insertions and deletions at arbitrary positions and you don't need random access or sequential scanning. Doubly-linked lists underpin LRU caches (think Go's container/list) for exactly this reason.

---

The Takeaway: Hardware Matters

Big-O notation is a powerful abstraction — but it hides constant factors and hardware behavior. Two algorithms with identical asymptotic complexity can differ by an order of magnitude in practice because of:

• Cache efficiency — are you accessing memory sequentially?
• Branch prediction — are your conditionals predictable?
• SIMD — can the compiler vectorize your loops?

The next time you're choosing a data structure, think not just about algorithmic complexity, but about where in memory your data lives and how the CPU will access it.

Your CPU is working very hard on your behalf. Give it contiguous memory and it will reward you.