Data Structures
Lessons · #2 of 11

Linked Lists

Nodes scattered through memory, stitched by pointers

Singly linked list · head → tail

init

Try it: Hit walk to chase the head pointer toward an index — count the hops. Then insert or delete at the same position — pointer rewires are O(1) but you still need to reach the spot.

Why it matters

Linked lists teach you to think in pointers - a fundamental concept in computer science. While often slower than arrays in practice, they unlock the door to understanding trees, graphs, and memory management.

The idea

Imagine a scavenger hunt. Each clue tells you where to find the next clue. You can't jump to clue #5 - you must follow the chain from the start.

That's a linked list. Each node contains data and a pointer to the next node.

The trade-off is inverted from arrays:

When you need to frequently insert/delete at the beginning or after a known node, linked lists win. When you need random access, arrays win.

Key takeaways

Going deeper

Singly vs doubly vs circular

| Variant | Each node has | Notable property | |---|---|---| | Singly-linked | next only | smallest memory; can only walk forward | | Doubly-linked | next + prev | O(1) delete given a node reference (no need to find prev); walk both ways | | Circular (singly or doubly) | tail → next = head | round-robin scheduling; iterator never ends | | XOR list (curiosity) | one pointer = prev XOR next | doubly-linked memory cost of singly. Breaks cache prefetch — academic. |

The killer feature of the doubly-linked list is the O(1) splice: given a node n you already have a pointer to, you can remove it from the list in two pointer writes:

n.prev.next = n.next;
n.next.prev = n.prev;

No traversal. This is why every LRU cache implementation under the sun uses a doubly-linked list backing a hash table: the hash table gives you O(1) lookup of the node by key; the doubly-linked list lets you O(1) move that node to the front on each access.

Circular variants underpin round-robin schedulers — every OS process scheduler that gives each runnable thread a time slice has a circular list somewhere. The "next" pointer from the last thread points back to the first; you just keep walking.

Memory overhead — the real numbers

A singly-linked list node holding an int32 on a 64-bit system:

[ 4 bytes data ][ 4 bytes padding ][ 8 bytes next pointer ] = 16 B

The data is 4 bytes, the storage is 16 bytes — 4× overhead per element. A doubly-linked list of the same data:

[ 4 bytes data ][ 4 bytes padding ][ 8 bytes next ][ 8 bytes prev ] = 24 B

6× overhead. And these nodes aren't sequential in memory — each is a separate heap allocation, so iterating the list is a cache-miss festival. The same int32s in a Vec<i32> pack into 4 bytes each, contiguous, prefetched by the CPU. For a million-element loop, the array can be 50–100× faster despite identical Big-O.

The lesson: linked lists are right when you genuinely need O(1) splice with a live node reference (LRU cache, OS scheduler, intrusive lists in kernel data structures). For everything else, prefer arrays — see the arrays lesson's cache-locality section.

Math details

Time Complexity
Access by index: O(n)
Insert at head: O(1)
Insert after node: O(1)
Delete node (given prev): O(1)
Search: O(n)
Space
Each node stores data + pointer(s)
Memory per node: sizeof(T) + sizeof(pointer)

Implementation

Linked List Node

struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

// Insert at head: O(1)
fn push_front(head: &mut Option<Box<Node<T>>>, data: T) {
    let new_node = Box::new(Node {
        data,
        next: head.take(),
    });
    *head = Some(new_node);
}

When to Use

Practice

Three classic linked-list problems, each highlighting a different pointer pattern:

→ Browse all practice problems