Linked Lists: Classic Theory, Brutal Hardware Reality

April 23, 2026 · Luciano Muratore

Linked Lists: Classic Theory, Brutal Hardware Reality

We all learn linked lists early. Dynamic nodes, easy insertion and deletion, no need to pre-allocate a fixed size. It is a classic data structure, and understanding it is fundamental. But once you move past the classroom and into real software, a natural question arises: where are linked lists actually used?

The honest answer, in modern C++, is: less often than you might think.

The Implementation

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

int main() {
    Node* head = new Node{10, nullptr};
    head->next = new Node{20, nullptr};
    head->next->next = new Node{30, nullptr};

    Node* temp = head;
    while (temp) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    return 0;
}

Each Node holds a value and a pointer to the next node. The list is built by chaining nodes together through the heap, and traversal follows the pointers one by one until nullptr is reached.

It is clean. It is intuitive. And in terms of teaching pointers and dynamic memory, it is hard to beat.

The Problem: Pointer Chasing

In theory, linked lists have attractive properties. Insertion and deletion at a known position are O(1)—no shifting elements, no reallocation. The list grows dynamically, one node at a time.

But theory does not account for the CPU cache.

Modern processors are fast, but memory access is not. To compensate, CPUs use a cache—a small, extremely fast layer of memory that stores recently accessed data and its neighbors. When you access one element in an array, the cache automatically loads the surrounding elements too. The next access is likely already in cache. This is cache locality, and it is why contiguous memory is fast.

Linked lists break this entirely. Each node is allocated separately on the heap, at an arbitrary memory address. When you follow a pointer from one node to the next, you jump to a completely different region of memory. The cache cannot predict where you are going. Every step is potentially a cache miss—a slow round-trip to main memory.

Those pointer chases add up. And at scale, they dominate.

Why std::vector Usually Wins

std::vector stores its elements contiguously in memory. Iterating over a vector means walking forward through a single, uninterrupted block. The CPU prefetcher loves this—it loads ahead, and most accesses are served from cache.

A linked list traversal, by contrast, is a series of unpredictable jumps. The prefetcher cannot help. You pay for each node access individually.

The result, in practice, is that std::vector outperforms linked lists for most sequential workloads—even for operations that linked lists are theoretically better at, like insertion in the middle. The cost of cache misses during traversal to find the insertion point often exceeds the savings from not shifting elements.

So When Do Linked Lists Make Sense?

There are real use cases. If you are doing frequent insertions and deletions at known positions—and you already have an iterator to that position—a linked list avoids the O(n) shift cost of a vector. std::list exists in the standard library for exactly this reason.

They also appear in low-level systems, memory allocators, and certain lock-free data structures where pointer-based construction is a deliberate design choice.

But for general-purpose sequential storage and iteration? The hardware has spoken.

Summary

• A linked list is a chain of dynamically allocated nodes, each holding data and a pointer to the next.
• Insertions and deletions at known positions are O(1)—no shifting required.
• Each node lives at an arbitrary heap address, causing cache misses on every pointer chase during traversal.
• std::vector stores elements contiguously, enabling the CPU cache to prefetch ahead and serve most accesses at cache speed.
• In practice, std::vector outperforms linked lists for most workloads, even some where linked lists have theoretical advantages.
• Final Insight: Theory says “dynamic.” Hardware says “stay contiguous.” Linked lists are essential for understanding memory and pointers—but when performance matters, the CPU cache is the data structure you are really programming for.