Arrays vs linked lists on real hardware

The textbook comparison

On paper, arrays and linked lists split the operations between them:

Read that way, the choice looks like a matter of which operations a program does most. Real measurements tell a different story: for nearly every workload, the array is faster, often by a large factor. The reasons are all things Big-O leaves out.

Reason 1: cache misses

The first module showed that memory arrives in 64-byte cache lines, and that a miss costs around a hundred times as much as a hit. The trace above applies that to both structures. The array's eight integers share one cache line: one miss, seven hits. The list's eight nodes, built over time, sit in eight different places: eight misses.

Worse, the list's misses are dependent. Node 1's address is stored in node 0, so the processor can't even ask for node 1 until node 0 arrives. A modern core can have ten or more independent misses in flight at once, but pointer chasing allows only one. And the hardware prefetcher, which predicts the next addresses of a sequential scan and fetches them early, has nothing to predict.

Nodes allocated one after another in a fresh program often do end up next to each other, and then a list behaves better than this. But after a program has run for a while, allocating and freeing memory, a list's nodes drift apart, and its performance drifts with them.

Reason 2: allocation

Every node is a separate allocation. Asking the allocator for memory costs time, typically tens of nanoseconds, and freeing it costs more, or creates work for a garbage collector. Appending a million elements to a dynamic array performs a few dozen allocations in total. Appending a million elements to a linked list performs a million.

Reason 3: memory overhead

A node carries more than its value. A C++ std::list<int> node holds two 8-byte pointers and a 4-byte int, padded to 24 bytes, plus whatever bookkeeping the allocator keeps per block. That is six or more times the size of the int itself. In Java, a LinkedList<Integer> node is an object with a header and three references, and the Integer it points to is another object. More bytes per element means fewer elements per cache line and per gigabyte, which brings back reason 1.

Stroustrup's experiment

Bjarne Stroustrup, the creator of C++, made this point with a simple experiment in a 2012 talk. Generate random integers and insert each one into a sequence at its sorted position; then remove elements from random positions one by one. The linked list's O(1) insertion looks like it should win. It didn't: std::vector was faster at every size he tried, and the gap grew as the sequence got longer.

The explanation is that both structures must first find the position, by walking from the start, and that walk is O(n) for both. For the vector, it is a fast, prefetched scan of contiguous memory, followed by a shift that moves contiguous memory with one memmove. For the list, it is a chain of dependent cache misses, followed by a cheap pointer update that saves almost nothing. Joshua Bloch, who wrote Java's LinkedList, has said publicly that he never uses it.

Where linked lists still win

None of this makes linked lists useless. They win when their O(1) operations are used without a search, or when their other properties matter:

• You already hold the node. In an LRU cache, a hash map hands you the exact node to move, so the doubly linked list's O(1) unlink and relink is the whole cost.
• Splicing. Moving a whole run of nodes from one list to another is a few pointer writes, whatever its length. An array would copy every element.
• Stable addresses. A node never moves once allocated, so pointers to it stay valid while others are inserted and removed. A dynamic array moves everything when it grows.
• Intrusive lists. In the Linux kernel and in many game engines, the next and prev fields live inside the objects themselves, so linking an object into a list allocates nothing, and one object can sit on several lists at once.
• Lock-free structures and persistent data. A list's head can be swapped atomically, which the expert level uses to build a lock-free stack. Functional languages share the tails of immutable lists between many versions.

A practical default

Start with a dynamic array. Use a deque when you need fast operations at both ends. Reach for a linked list when one of the situations above applies, and measure if you aren't sure. The practice lab for this lesson repeats Stroustrup's experiment so you can see the numbers on your own machine.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Arrays vs linked lists on real hardware from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

function reverse_and_find_mid(head):
    slow = head; fast = head
    while fast != null and fast.next != null:
        slow = slow.next
        fast = fast.next.next
    prev = null; curr = slow
    while curr != null:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};
 
ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head;
    while (curr != nullptr) {
        ListNode* nxt = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nxt;
    }
    return prev;
}

public class LinkedListSolver {
    public static class ListNode {
        int val; ListNode next;
        ListNode(int v) { this.val = v; }
    }
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode nxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
    }
}

class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None) -> None:
        self.val = val
        self.next = next
 
def reverse_list(head: ListNode | None) -> ListNode | None:
    prev, curr = None, head
    while curr is not None:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.