root.system / 0x0C / structure

A chain of somewheres.

An array is houses on a numbered street. A linked list is a treasure hunt: each node tells you, by address, where the next one lives. You give up the array's cheap indexing and cache locality. In return you get O(1) inserts and deletes anywhere, no resizing, no copying. That tradeoff has been keeping operating systems, schedulers, and lock-free queues alive for fifty years.

Beginner// level 01

Linked lists as a chain of nodes

Picture a row of post-it notes on a wall. Each note has a number on it, and an arrow drawn to wherever the next note happens to be: across the room, behind the couch, anywhere. To read them in order, you start at the first one and follow the arrows. That's a linked list.

A linked list is:

  • A chain of nodes, each one allocated separately.
  • Every node holds a value and a pointer to the next node.
  • The last node's next pointer is null (no next).
  • The whole list is referenced by a head pointer at the start.

Notice what's missing: there's no rule that says nodes are next to each other in memory. Each one lives wherever the allocator put it. The "ordering" exists only in the pointers, not in the addresses.

A picture of a singly linked list

SINGLY LINKED LISTheadanextbnextcnextdnext∅each node lives wherever the allocator put it: next is a heap address, not an offset

Compare that to the array picture: same four values, but no contiguous block. Every next is a 64-bit heap address, not an offset. Walking the list is a sequence of pointer chases: read a node, follow its next, read the next node, follow its next, and so on.

// the head pointer is the whole list
In C the entire list is just one Node *head. In Rust it's an Option<Box<Node>>. Either way, that single pointer is enough; the rest of the list is reachable by following next from there. Lose the head pointer and you've leaked the list.

Build one and walk it

Rust• • •
// A singly linked list of i32, written from first principles.
// Each node owns a heap-allocated Box pointing at the next node.
enum List {
    Cons(i32, Box<List>),
    Nil,
}

use List::{Cons, Nil};

fn main() {
    // Build  10 -> 20 -> 30 -> Nil
    let list = Cons(10,
              Box::new(Cons(20,
              Box::new(Cons(30,
              Box::new(Nil))))));

    // Walk it. Each step is a pointer dereference into the heap.
    let mut cursor = &list;
    while let Cons(value, next) = cursor {
        println!("{value}");
        cursor = next;
    }
}
C• • •
#include <stdio.h>
#include <stdlib.h>

// The classic C linked-list node. value + pointer to the next.
typedef struct Node {
    int value;
    struct Node *next;
} Node;

int main(void) {
    // Build 10 -> 20 -> 30 -> NULL, one malloc per node.
    Node *c = malloc(sizeof *c); c->value = 30; c->next = NULL;
    Node *b = malloc(sizeof *b); b->value = 20; b->next = c;
    Node *a = malloc(sizeof *a); a->value = 10; a->next = b;

    // Walk it. Pointer chase, one node at a time.
    for (Node *p = a; p != NULL; p = p->next)
        printf("%d\n", p->value);

    // Each node was allocated separately; each one has to be freed.
    free(a); free(b); free(c);
    return 0;
}
// why this looks heavier than the array version
Three nodes means three mallocs in C, and three Box::news in Rust. Each one calls into the allocator, each one returns a 64-bit pointer. The "list" itself is the head plus those three heap blocks. Pause and feel that cost: a five-element Vec<i32> is one heap block. A five-element linked list is five heap blocks plus a head pointer.
// connect back to the memory page
Every next pointer is a heap address, the kind described in the memory page's stack-vs-heap section. The head pointer lives on the stack (it's a local in main), but the nodes it leads to all live on the heap. That's why building a linked list is allocator-heavy: each malloc / Box::new is a separate trip into the allocator, with the bookkeeping cost the memory page warned about. A Vec pays that price once and re-uses the buffer; a linked list pays it on every push.
Intermediate// level 02

How inserts and deletes actually work

The whole appeal of a linked list is the operations on its middle. Inserting a value into the middle of an array means shifting every element after the insertion point. Inserting a value into the middle of a linked list means writing two pointers. No neighbours move.

Insertion: splice a node in

BEFORE: a → canextcnextAFTER: a → b → canextbnextcnextone allocation for the new node, two pointer writes, no neighbours movedsame operation on an array would shift every element after the insertion point

To insert b between a and c:

  1. Allocate the new node and put b's value in it.
  2. Set the new node's next to whatever a.next currently is (i.e. c).
  3. Set a.next to the new node.

That's it. One allocation, two pointer writes. The cost doesn't depend on how long the list is. It's O(1) once you've got a reference to the predecessor. The catch is that "one allocation": the memory page warned that a heap allocation is hundreds to thousands of cycles, while the pointer writes are one each. The big-O is constant, but the constant is the allocator.

Rust• • •
// Insert a node after a given position. O(1) once you have the
// predecessor; getting there is O(n) if you start from the head.
struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

fn insert_after(prev: &mut Node, value: i32) {
    // Splice the new node in: take prev's old next, hand it to the new
    // node, then point prev at the new node. Two pointer writes.
    let old_next = prev.next.take();
    let new_node = Box::new(Node { value, next: old_next });
    prev.next = Some(new_node);
}

fn main() {
    let mut head = Node {
        value: 10,
        next: Some(Box::new(Node { value: 30, next: None })),
    };
    // Insert 20 between 10 and 30.
    insert_after(&mut head, 20);

    let mut cursor = Some(&head);
    while let Some(n) = cursor {
        println!("{}", n.value);
        cursor = n.next.as_deref();
    }
}
C• • •
#include <stdio.h>
#include <stdlib.h>

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

// Insert a new node right after `prev`. No nodes are shifted.
void insert_after(Node *prev, int value) {
    Node *n = malloc(sizeof *n);
    n->value = value;
    n->next  = prev->next;   // splice: new -> what prev used to point at
    prev->next = n;          // and prev now points at new
}

int main(void) {
    Node *c = malloc(sizeof *c); c->value = 30; c->next = NULL;
    Node *a = malloc(sizeof *a); a->value = 10; a->next = c;

    // Insert 20 between 10 and 30. O(1): only two pointer writes.
    insert_after(a, 20);

    for (Node *p = a; p != NULL; p = p->next) printf("%d\n", p->value);

    // (cleanup elided for brevity)
    return 0;
}

Deletion: bypass and free

BEFORE: a → b → canextbnextcnextAFTER: a ↷ c  (b freed)anextbnextfreedcnextone pointer write on the predecessor, one free() call, every other node stays put

To delete b from the middle of the list:

  1. Find b's predecessor (here, a).
  2. Point the predecessor's next at b.next instead of b.
  3. Free b.

Same shape as insert: one pointer write on the predecessor, one free. Every other node stays exactly where it was.

The complexity table everyone memorises

operationarray / Vecsingly linkeddoubly linked
random access arr[i]O(1), address mathO(n), walk the chainO(n), walk the chain
push at endamortised O(1)O(n); needs the tail, unless you keep oneO(1) with a tail pointer
push at frontO(n), shift everythingO(1)O(1)
insert at middle (given node)O(n), shift the suffixO(1)O(1)
delete at middle (given node)O(n), shift the suffixO(n); need predecessorO(1); predecessor is one hop away
iteratevery fast, cache friendlyslow: pointer chase, cache missesslow: same, plus extra bytes

Singly linked vs doubly linked

DOUBLY LINKED LIST∅prevanextprevbnextprevcnext∅twice the pointer bytes per node: bidirectional traversal, O(1) delete given a node reference

A doubly linked list adds a prev pointer to every node. The cost is one extra pointer per node: 8 bytes on a 64-bit system. The benefit is two:

  • You can walk the list backwards as well as forwards.
  • Given a reference to any node, you can delete it in O(1) without first finding its predecessor; the predecessor is just node.prev.

That second property is why every "list with an index" structure ends up doubly linked. The LRU cache pattern (HashMap<K, &Node> + doubly linked list) is the canonical example, and it shows up in CPU caches, browser caches, and database buffer pools.

Rust• • •
// A doubly linked list is the same idea with a backward pointer too.
// Note: a safe Rust DLL needs Rc<RefCell<...>> or unsafe pointers
// because each node has two owners. This is the cleanest sketch.
use std::cell::RefCell;
use std::rc::{Rc, Weak};

struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
    prev: Option<Weak<RefCell<Node>>>, // Weak: avoid a cycle in refcounts
}

// Building a doubly linked list in safe Rust is genuinely awkward.
// In production code, reach for std::collections::LinkedList<T> or,
// more often, a Vec + indices acting as "pointers" into the same Vec.
C• • •
#include <stdlib.h>

// A doubly linked node. Two pointer fields instead of one.
typedef struct DNode {
    int value;
    struct DNode *prev;
    struct DNode *next;
} DNode;

// Insert a node right after `prev`. Update four pointers.
void dll_insert_after(DNode *prev, int value) {
    DNode *n = malloc(sizeof *n);
    n->value = value;
    n->prev  = prev;
    n->next  = prev->next;
    if (prev->next) prev->next->prev = n;
    prev->next = n;
}

// Remove a node from anywhere. O(1) given the node itself; no traversal.
void dll_remove(DNode *node) {
    if (node->prev) node->prev->next = node->next;
    if (node->next) node->next->prev = node->prev;
    free(node);
}
// why doubly linked lists are awkward in safe Rust
Each node has two references to it (from its predecessor and its successor), and they're both mutable. Rust's borrow checker is allergic to that. The escape hatches are Rc<RefCell<...>> with Weak back-pointers, or raw unsafe pointers. In practice, Rust programmers reach for Vec + indices far more often than they reach for a literal doubly linked list. The standard library's LinkedList<T> exists but is rarely the right tool.
Advanced// level 03

Cache cost, intrusive lists, and where linked lists actually live

The cache cost, made concrete

The arrays page made the case already, but it bears repeating in the opposite direction. Walking an array of N ints is essentially N reads, almost all of which hit L1 cache because the CPU fetched whole cache lines and prefetched the next ones. Walking a linked list of N ints is N pointer chases. The CPU has no idea where the next node lives until it has read the current one's next field. Hardware prefetch can't help. Every step is a potential cache miss.

The numbers are sobering. A modern L1 hit is roughly 4 cycles. A main-memory fetch is 200-300 cycles, the memory hierarchy from the memory page, end to end. A linked list traversal can be two orders of magnitude slower than an array traversal of the same length, even though both are O(n). This is the most important "big-O lies" example to internalise.

It gets worse over time. A long-running program that does many malloc / free cycles ends up with heap fragmentation: the allocator returns free regions wherever it can find them, and the nodes of a list that was built incrementally end up scattered across the whole heap. The same list at startup might fit in a handful of cache lines; a week later it can be sprayed across megabytes of memory. The arrays page calls this locality, the memory page calls it fragmentation, and a linked list pays the price for both.

// rule of thumb
If you're going to iterate the collection, prefer a Vec. If you're going to splice middle elements in and out a lot, and you have a stable pointer to where you want to splice, a linked list earns its keep. Most code does more iterating than splicing, which is why Vec wins by default.

The other escape: arena-allocated lists

You can have the linked-list shape without paying for the linked-list allocation pattern. The trick: store every node inside one big Vec (an arena), and use indices into that Vec where you would have used pointers.

  • Same O(1) splices, because changing a "next" still only touches two slots.
  • Far better cache behaviour, because all the nodes live next to each other in one contiguous buffer.
  • Smaller "pointers": 32-bit indices instead of 64-bit addresses.
  • No malloc per node; one big amortised allocation.

This is how the Linux kernel, game-engine ECS systems, and lock-free queues actually represent their lists. It is almost always what you want when you reach for a linked list in Rust.

Rust• • •
// "Linked list" without any malloc per node. The arena owns the
// storage; indices play the role of pointers.
//
// This is how serious systems do it: the OS scheduler, the Linux
// kernel's task_struct list, ECS game engines, lock-free queues.
struct Arena {
    nodes: Vec<Node>,
}

#[derive(Clone, Copy)]
struct NodeId(usize);

struct Node {
    value: i32,
    next: Option<NodeId>,
}

impl Arena {
    fn push(&mut self, value: i32, after: Option<NodeId>) -> NodeId {
        let id = NodeId(self.nodes.len());
        self.nodes.push(Node { value, next: None });
        if let Some(prev) = after {
            self.nodes[id.0].next = self.nodes[prev.0].next;
            self.nodes[prev.0].next = Some(id);
        }
        id
    }
}

// Three reasons this layout is usually faster than the heap version:
//  1. One contiguous Vec: far better cache behaviour on iteration.
//  2. One allocation amortised, not one per node.
//  3. Indices are 32-bit; pointers are 64-bit. Half the metadata.
C• • •
#include <stdint.h>

// Same idea in C: nodes live in one array, "pointers" are 32-bit indices.
#define ARENA_CAP 1024
#define NIL UINT32_MAX

typedef struct {
    int      value;
    uint32_t next;       // index into arena, or NIL
} ANode;

static ANode    arena[ARENA_CAP];
static uint32_t arena_len = 0;

uint32_t a_alloc(int value, uint32_t after) {
    uint32_t id = arena_len++;
    arena[id].value = value;
    arena[id].next  = NIL;
    if (after != NIL) {
        arena[id].next     = arena[after].next;
        arena[after].next  = id;
    }
    return id;
}

Intrusive lists: the OS kernel's favourite trick

One more pattern, and it's the one you'll see everywhere in serious systems code. An intrusive linked list moves the next (and optionally prev) pointers into the data type itself, instead of wrapping the data in a list node.

So a Linux task_struct (a process) contains:

  • The actual process state (pid, signals, file handles, scheduler info…)
  • A field struct list_head tasks; that links it into the global process list.
  • Another field struct list_head children; that links it into its parent's children list.
  • And so on. The same struct lives in many lists at once.

The benefit: no allocation overhead per "list node" because the node is the data. The downside: the data type has to know about the list. In C this is idiomatic; in Rust it requires unsafe or specialised crates.

Where linked lists actually win

operating systems
Run queues, wait queues
The kernel scheduler maintains queues of runnable and blocked tasks. Tasks move between them constantly (every syscall, every interrupt). Intrusive doubly linked lists make this O(1) with no allocation in the hot path.
memory allocators
Free lists
Allocators like <code>malloc</code> and <code>jemalloc</code> maintain linked lists of free memory blocks of each size class. Allocation pops from the head, deallocation pushes onto the head; both O(1), both lock-free with the right design.
concurrency
Lock-free queues
MPSC and SPSC queues used in Tokio, in Rust's <code>std::sync::mpsc</code>, and in every game engine's job system are linked lists internally. The compare-and-swap on the head pointer is the whole synchronisation story.
LRU caches
Hash + doubly linked list
Every cache that evicts "least recently used" (CPU caches, OS page caches, your browser's resource cache, Redis with <code>maxmemory-policy allkeys-lru</code>) is a hashmap pointing into a doubly linked list of cache entries.

When the answer is just 'don't'

A linked list is almost never the right answer to "I have a list of things". For that, you want a Vec, full stop. Use a linked list when one of these is true:

  • You will splice middle elements in and out of the structure frequently, and the splices dominate any iteration cost.
  • You need stable references that survive other elements being added or removed.
  • You're building an intrusive list where the node is the data.
  • You're doing lock-free concurrent work that depends on atomic pointer swaps.

If none of those are true, a Vec or a VecDeque will beat a linked list on every dimension that matters.

Where to dig in next

Linked lists are the gateway to most of the interesting data-structure landscape:

  • Skip lists. Probabilistic, sorted, O(log n) operations, the basis of Redis sorted sets and many lock-free maps.
  • Persistent / immutable lists. The cons cell from Lisp, the spine of Haskell, and the structural-sharing trick that makes Clojure's collections work.
  • Lock-free linked lists (Harris, Michael & Scott). The compare-and-swap algorithms behind java.util.concurrent and Rust's crossbeam.
  • Linux's list_head. Read include/linux/list.h for the canonical intrusive-list API; the macros are short and beautiful.
  • "Learning Rust With Entirely Too Many Linked Lists". The single best resource for understanding why linked lists are hard in Rust, and what to do about it.
next up / 0x0D
Turn anything into a fingerprint. Hash maps, Merkle trees, blockchain.
hashing →