When to Use Linked Lists vs Arrays

The Big-O Illusion

Open any introductory data-structures course and you will be told the same story. Inserting at the head of a singly linked list is $O(1)$; inserting at the head of a dynamic array is $O(n)$ because every existing element must shift one slot. Therefore, the story concludes, when you need many head-insertions, the linked list wins. Every freshman accepts this. Every senior engineer knows it is wrong in practice for almost every realistic workload.

Big-O describes how the cost scales as $n$ grows. It does not describe what one operation actually costs. It hides the constant factor — and on modern hardware, that constant factor is dominated by the memory hierarchy, not by the arithmetic. A linked-list head-insert is $O(1)$, but the "1" includes a heap allocation (~30-100 ns) and a future cache miss the next time anyone walks the list (~100-300 cycles). An array shift moves $n$ elements, but each move is a sequential memory copy at roughly $1$ cycle each, fully prefetched, vectorized to 32-64 bytes per cycle by SIMD.

Stroustrup's Benchmark: Vector Beats List

In a now-famous 2012 GoingNative talk, Bjarne Stroustrup, the creator of C++, ran the following experiment. Given $n$ random integers, insert them one at a time into a sorted sequence — that is, for each new value find the right position and put it there. Repeat for two containers: std::vector<int> and std::list<int>. Both are $O(n^2)$ algorithms. On paper they should scale identically.

The vector loses on the algorithmic accounting: each insertion does an $O(\log n)$ binary search to find the position, then shifts up to $n$ elements. The linked list looks better: $O(n)$ linear search to find the position, then $O(1)$ splice. Beginners predict the linked list wins.

Stroustrup's measurement said the opposite. From $n = 100$ all the way past $n = 500{,}000$, the vector won by an enormous margin — often 10x to 50x faster. The gap widened, not narrowed, as $n$ grew. The linked-list version was so much slower that it stopped being practical before $n$ hit a million.

The takeaway: the vector pays for shifting, but the shift is cache-friendly contiguous memmove. The linked list pays for pointer chasing on every comparison during the search, and every pointer chase is a potential cache miss. The vector's expensive operation is fast; the linked list's cheap operation is slow.

Why Cache Locality Wins

Modern CPUs are roughly $100\times$ faster than main memory. To hide that gap, every CPU has a cache hierarchy:

Memory is moved between these levels in cache lines of 64 bytes each. When you read one int, you actually pull 16 ints. Sequential array traversal therefore amortizes one DRAM round-trip across 16 elements; the next 15 are essentially free. Linked-list traversal jumps to a fresh address every node, defeating the cache line and the hardware prefetcher simultaneously.

There is one more layer: the prefetcher. Modern CPUs detect striding access patterns and pull cache lines before they are requested. This works beautifully for arrays — the prefetcher quickly identifies a +4 stride and stays a few lines ahead — and not at all for linked lists, because the prefetcher cannot guess where the next pointer leads until the current load returns.

The Decision Framework

With the constant-factor reality established, here is the decision rule a senior engineer actually uses. Choose a linked list only if all four of these are true.

1. You will frequently insert or delete at known positions — that is, you already hold a node pointer. (If you only have an index, the linked list must walk to find the position, and then you have lost.)
2. You will rarely need indexed random access (list[k]).
3. The list is long enough that the algorithmic $O(1)$ splice actually pays back the per-node cache penalty — empirically, this means many thousands of nodes and the splices outnumber the traversals by a wide margin.
4. You don't need iteration over the whole list to be fast.

Choose a dynamic array when:

• You need indexed access.
• Sequential traversal is on the hot path.
• The set of elements is bounded or growth is rare.
• Cache misses matter — i.e., always.

Choose a deque (a doubly linked list of fixed-size blocks) when:

• You need fast push and pop on both ends.
• You don't want the pointer-invalidation hazards of a vector.
• You want most of the array's cache friendliness within each block.

Choose a hash map plus doubly linked list (the LRU pattern) when:

• You need $O(1)$ random access by key.
• You also need $O(1)$ reordering — move-to-front, evict-tail.

Choose a balanced BST or skip list when:

• You need $O(\log n)$ insert, delete, search, and predecessor/successor. An array can search in $O(\log n)$ but cannot insert in $O(\log n)$; a linked list can splice but cannot search faster than $O(n)$. Only ordered tree-like structures unify all four.

Choosing the Right Container

Here is the decision flow, in the order an experienced engineer applies it.

1. Do you only need a sequence and indexed access? Use a dynamic array. Stop here. This covers ~70% of all real cases.
2. Do you need O(1) push/pop on both ends? Use a block deque (Python collections.deque, Java ArrayDeque, C++ std::deque). Cache-friendly within blocks, no end-shifting.
3. Do you need O(1) lookup by key? Use a hash map. Plus a DLL if you also need O(1) ordered eviction (LRU).
4. Do you need ordered logarithmic ops (predecessor, range, k-th smallest)? Use a balanced BST or skip list.
5. Do you need a persistent / immutable structure? A linked list shines here, because tail-sharing is free — but you are now in a functional-programming context, not a performance one.
6. None of the above and you genuinely have node pointers everywhere? Now consider a doubly linked list.

Memory and Locality, Quantified

Concrete numbers for one million 32-bit integers, on a typical x86-64 CPU with 64-byte cache lines:

The verdict is stark. The linked list trades a 30 to 100x per-element constant factor for the asymptotic $O(1)$ splice. That trade pays only when splices dominate traversals, which is rarer than students think.

The Intrusive Linked List Pattern

When linked lists do appear in production code — particularly in operating systems, schedulers, and high-performance networking — they are almost always intrusive. Instead of a wrapper node holding a pointer to the payload, the link pointers are embedded inside the payload struct.

1/* Linux-kernel-style intrusive doubly linked list. */
2struct list_head {
3    struct list_head *prev, *next;
4};
5
6/* The payload owns its links. */
7struct task {
8    int pid;
9    char name[32];
10    struct list_head runqueue;   /* link in scheduler's run queue */
11    struct list_head children;   /* link in parent's child list */
12};

Two payoffs. First, no separate allocation per insertion — the link cell is already inside the task struct, allocated when the task was created. Second, the same object can sit on multiple lists by embedding multiple list_head fields. The Linux kernel uses this pattern thousands of times: the struct task for a process simultaneously lives on the run queue, its parent's children list, the global pid hash bucket, and more — all without a single auxiliary allocation.

Even with intrusive lists, the kernel pairs them with a hash table for fast lookup by id. The list is the auxiliary thread used for ordered iteration and O(1) splicing; the hash table is the primary index. This is the lesson from real systems: linked lists are rarely the primary container; they are almost always a secondary thread woven through a primary hash or array.

Engineering Case Studies

LRU cache: hash + DLL

An LRU cache stores at most $K$ items keyed by string, evicting the least recently used when a new item arrives. Two operations must be $O(1)$: get(key) and put(key, value). The textbook solution combines a hash map with a doubly linked list. The hash map maps keys to DLL nodes; the DLL orders nodes by recency. get hashes the key (O(1)), splices the node to the front (O(1)). put hashes (O(1)) and, if full, evicts the tail (O(1)). Neither an array nor a DLL alone can do this; the combination is essential. This is the design of Python's functools.lru_cache and Redis's eviction policy.

Queue: circular array, not linked list

For a FIFO queue, the textbook answer is "use a linked list because both ends are O(1)." The production answer is "use a circular array." Python's collections.deque is a doubly linked list of 64-element blocks; Java's ArrayDeque is a power-of-two circular buffer. Both are 5 to 10x faster than a hand-rolled linked list for the same operations because most pushes and pops hit cached memory inside the current block.

Undo stack: dynamic array

An editor maintains an undo stack of the last $N$ commands. Operations are push and pop at one end. A list in Python or Vec in Rust does this perfectly with $O(1)$ amortized push and $O(1)$ pop. Reaching for LinkedList here is overkill; you pay the per-node allocation tax for no asymptotic benefit.

Browser tab list: array of tab objects

Tabs are reordered rarely (drag-and-drop) and traversed often (rendering, keyboard navigation). The reorder is human-paced, so a linear shift of 30 tabs is invisible — sub-microsecond. The traversal happens every paint frame, so cache locality matters. Array wins; linked list loses.

OS process scheduler: depends on the era

Classical Unix used a circular doubly linked list per priority level. Modern Linux's Completely Fair Scheduler (CFS) instead uses a red-black tree keyed by accumulated CPU time, because it needs $O(\log n)$ "pick the task with minimum runtime" queries that a flat list cannot serve efficiently. Same problem, different data structure as the requirements grew.

Database B-tree leaves: linked together

InnoDB, Postgres, SQLite, and most other B-tree-based engines keep their leaf pages connected by sibling pointers — a singly or doubly linked list at the leaf level. Why? Because range queries (WHERE x BETWEEN a AND b) descend to the leaf containing a once, then walk leaves sequentially. The linked list is the auxiliary thread that turns range queries from $O(k \log n)$ into $O(\log n + k)$. This is the canonical secondary-thread pattern from earlier — the B-tree is the primary index, the list is the fast iterator.

A Two-Language Benchmark

Talk is cheap. Run this on your machine and watch the constant factor crush Big-O.

1import time
2from dataclasses import dataclass
3
4@dataclass
5class Node:
6    value: int
7    next: "Node | None" = None
8
9def append_array(n: int) -> float:
10    arr = []
11    t0 = time.perf_counter()
12    for i in range(n):
13        arr.append(i)
14    return time.perf_counter() - t0
15
16def append_linked(n: int) -> float:
17    head: Node | None = None
18    tail: Node | None = None
19    t0 = time.perf_counter()
20    for i in range(n):
21        node = Node(i)
22        if tail is None:
23            head = tail = node
24        else:
25            tail.next = node
26            tail = node
27    return time.perf_counter() - t0
28
29def sum_array(arr: list[int]) -> tuple[int, float]:
30    t0 = time.perf_counter()
31    total = 0
32    for x in arr:
33        total += x
34    return total, time.perf_counter() - t0
35
36def sum_linked(head: "Node | None") -> tuple[int, float]:
37    t0 = time.perf_counter()
38    total = 0
39    cur = head
40    while cur is not None:
41        total += cur.value
42        cur = cur.next
43    return total, time.perf_counter() - t0
44
45if __name__ == "__main__":
46    N = 1_000_000
47    print(f"append array  ({N:,}): {append_array(N):.3f}s")
48    print(f"append linked ({N:,}): {append_linked(N):.3f}s")

Same experiment in C++, where the difference is even larger because the absolute cost of memory access is a bigger fraction of the total work.

1// g++ -O2 -std=c++20 bench.cpp && ./a.out
2#include <chrono>
3#include <forward_list>
4#include <iostream>
5#include <vector>
6using clock_hr = std::chrono::high_resolution_clock;
7
8template <class F>
9double seconds(F&& f) {
10    auto t0 = clock_hr::now();
11    f();
12    return std::chrono::duration<double>(clock_hr::now() - t0).count();
13}
14
15int main() {
16    constexpr int N = 1'000'000;
17
18    std::vector<int> v;
19    v.reserve(N);
20    double t_v = seconds([&] {
21        for (int i = 0; i < N; ++i) v.push_back(i);
22    });
23
24    std::forward_list<int> l;
25    double t_l = seconds([&] {
26        for (int i = 0; i < N; ++i) l.push_front(i);
27    });
28
29    long long sum_v = 0;
30    double s_v = seconds([&] {
31        for (int x : v) sum_v += x;
32    });
33
34    long long sum_l = 0;
35    double s_l = seconds([&] {
36        for (int x : l) sum_l += x;
37    });
38
39    std::cout << "vector  build " << t_v*1000 << " ms, traverse " << s_v*1000 << " ms\n";
40    std::cout << "fwdlist build " << t_l*1000 << " ms, traverse " << s_l*1000 << " ms\n";
41}

On a 2024 laptop, typical results: vector traverse $\approx 0.5$ ms, forward_list traverse $\approx 20$ ms — a 40x ratio for two algorithms with identical $O(n)$ complexity. The difference is the memory hierarchy.

Interactive: Pick the Right Structure

Five real-world workloads. For each one, pick the container that an experienced engineer would actually choose, then read why.

Containers in the Wild

How standard libraries actually expose these trade-offs:

Two patterns jump out. First, every modern language ships a dynamic array as the default sequence, because that is the right answer ~70% of the time. Second, several languages either omit the linked list entirely (Python, JS/TS) or warn against it (Rust's docs literally say "you almost always want Vec or VecDeque"). The ecosystem has spoken: linked lists are a niche tool.

Pitfalls in Choosing

• Reflexively reaching for LinkedList from intro classes. The course said it was $O(1)$ at the head, so it must be fast. It isn't. Always benchmark before committing.
• Believing Big-O without measuring. Two $O(n)$ algorithms can differ by 100x on real hardware. Big-O ranks scaling, not speed.
• Premature pointer-itis. "I might need to splice in the middle someday" is the most expensive sentence in performance engineering. Profile real workloads, not imagined ones.
• Java LinkedList. It implements both List and Deque, which makes it look like a universal answer. It is almost never the right answer. Use ArrayList or ArrayDeque.
• Forgetting allocator pressure. Every new linked-list node is a malloc/new — slow on its own and fatal under contention from many threads. Arena and slab allocators help, but they push the complexity onto you.
• Ignoring the auxiliary index. If you need both fast lookup and fast splicing, you need both a hash map and a list — not one or the other. The LRU cache is the archetype; copy it.
• Using a linked list where a deque belongs. If you only need both-ends operations, a block deque is faster, simpler, and more cache-friendly. A linked list is overkill for queues and stacks.

Quick Checks