Linked Lists

The shape

A linked list is a sequence of nodes. Each node holds a value and a pointer to the next node. The list itself is a pointer to the first node (the "head"). The last node's "next" pointer is null.

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

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

// to walk the list:
for (Node* n = head; n; n = n->next) {
    std::cout << n->value;
}

Compare to an array: int arr[] = {10, 20, 30}. Same data, but the array packs them in 12 contiguous bytes, while the linked list scatters them across the heap, each node 16+ bytes (value + pointer + allocator overhead).

The trade-off

Linked lists are theoretically better at:

• Inserting/deleting in the middle — O(1) once you have an iterator pointing there. Arrays need O(n) to shift elements over.
• Splicing — moving a chunk from one list to another in O(1). Just rewire pointers.
• Growing without ever copying — each new node is its own allocation; the list never relocates.

Linked lists are dramatically worse at almost everything else:

• Random access: O(n). To get the 100th element, you walk 100 pointers.
• Sequential traversal: still O(n) but with cache misses on every step (Week 3). Walking a million-element list can be 10–100× slower than walking a million-element vector.
• Memory overhead: 8–16 bytes per node beyond the value itself. For a list of ints, that's a 4× memory cost.
• Allocator pressure: every insert is a heap allocation.

The textbook says "use a linked list if you do lots of inserts/deletes". Reality says "even then, a vector is usually faster up to several thousand elements, because cache effects swamp the algorithmic advantage". The classic advice is wrong on modern hardware.

When to actually reach for one

• You're holding tens of thousands of elements and doing lots of mid-list inserts/deletes and never need random access.
• You need O(1) splice between two collections.
• You need iterator stability — pointers/iterators that don't get invalidated when other elements are inserted or removed.
• You're implementing a low-level data structure (kernel free-list, intrusive list inside another data structure).

For everything else: std::vector.

Doubly linked, circular, and intrusive

Variations exist:

• Doubly linked (std::list): each node has both next and prev. You can walk in either direction; deletion of a known node is O(1).
• Circular: the last node's next points back to the head. Useful for ring buffers, round-robin schedulers.
• Intrusive: the "next" pointer lives inside the value type, not in a wrapper node. Saves an allocation per element. Common in OS kernels and game engines (Linux's kernel uses these everywhere).

Why this matters for AI

Almost nowhere — and that's the point. AI workloads are vector- and matrix-heavy, and contiguous memory access is everything. You'd struggle to find a linked list in any modern AI framework's hot path. Where they appear at all is in metadata structures (the operator dependency graph, the training callback chain) where O(1) splicing is occasionally useful.

Linked lists: famous, often wrong. Reach for a vector first.

What's next

Two simple data structures with very specific access patterns — and surprisingly profound applications.

Week 35 is Stacks & Queues.