I Tried to Build a Linked List in Rust. The Borrow Checker Had Other Plans

Part of the Data Structures in Rust series.

There is a rite of passage every Rust learner goes through, usually within the first month, and it has nothing to do with lifetimes or async. It is trying to build a linked list. You have written one in Java or Python a hundred times, it takes maybe ten minutes, a next pointer and you are done. In Rust, the same exercise turns into an afternoon of staring at error messages that all say roughly the same thing in increasingly creative ways: you cannot have what you are trying to have.

This isn’t a skill issue. It’s intentional. A linked list, as you would naturally write it, violates Rust’s ownership rules in a way that no amount of cleverness fixes. Understanding exactly why is one of the fastest ways to actually internalize what ownership means, because the failure is not subtle. It is structural. If ownership itself is still fuzzy, the longer breakdown is here.

The naive attempt and why it cannot exist

Here is what every Java or Python programmer reaches for first.

struct Node {
    value: i32,
    next: Node, // this will not compile
}

This fails immediately, and the error has nothing to do with borrowing. Node contains a Node, which means the size of Node depends on the size of Node, which depends on the size of Node, forever. Rust needs to know the size of every type at compile time to allocate it on the stack, and a type that contains itself has no fixed size. Java does not hit this problem because every object reference in Java is a pointer under the hood, a fixed-size address, regardless of what the object actually contains. Rust shows you that indirection explicitly instead of hiding it, and the moment you try to nest a type inside itself without that indirection, the compiler stops you cold.

The fix everyone reaches for next is wrapping the next node in something that has a fixed size regardless of what it points to.

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

Box<Node> is a pointer to heap-allocated data, so its size is just the size of a pointer, fixed and known. Option wraps it so the last node can have None instead of pointing to another node. This compiles. This is also where most tutorials stop, satisfied, having shown you a singly linked list with Box. It is also where the real problems start if you try to do anything more interesting than insert at the head.

Where it falls apart: removing a node from the middle

Insertion at the head is easy. You create a new node, set its next to the old head, and the new node becomes the head. No ownership conflicts because nothing needs to be borrowed from two places at once.

Removing a node from the middle of the list is where the structure actively fights you. To remove a node, you need to take the node before it, change its next pointer to skip over the node being removed, and point it at the node after. That means you need mutable access to the previous node and the node being removed at the same time, while also reasoning about the node after it.

fn remove(&mut self, target: i32) {
    let mut current = &mut self.head;

    while let Some(node) = current {
        if node.value == target {
            // We need to take ownership of node.next here,
            // but `node` is borrowed through `current`,
            // and `current` is borrowed from `self.head`.
            // The compiler will not let you do what feels obvious:
            // *current = node.next.take(); // works because take() moves the value out,
            // leaving None behind, so nothing is borrowed twice
            return;
        }
        current = &mut node.next;
    }
}

The comment in that snippet is doing real work. node.next.take() compiles because Option::take() replaces the value with None and hands you ownership of what was there, which sidesteps the borrow conflict by ending the borrow before you assign. But arriving at that solution from first principles, without already knowing the trick, is exactly the wall every Rust newcomer hits. You want to walk a chain of mutable references while also occasionally replacing pieces of that chain, and Rust's borrow checker is built around the rule that you cannot hold a mutable reference while any other reference to the same value exists. Walking a linked list with mutable references means each step potentially invalidates the reference you held a moment ago.

Why doubly linked lists are worse, not just harder

A doubly linked list needs each node to point both forward and backward. In Java, this is trivial: every node holds a reference to the next node and a reference to the previous node, and both directions are just pointers, no ownership questions asked because Java’s garbage collector cleans up whatever nobody points to anymore.

Rust’s default ownership model assumes a single owner for every value. A doubly linked list wants two owners for the same node: the node before it, which owns the forward link, and the node after it, which owns the backward link. That assumption is not designed to express “this value has two things that need to reach it.” Rc<RefCell<Node>> is the usual workaround, shared ownership through reference counting combined with interior mutability so you can still modify the node through a shared reference. It works. It also means every single access to a node now goes through a RefCell borrow check at runtime, which can panic if you accidentally hold two mutable borrows at once, the exact bug class the compile-time borrow checker exists to prevent, now pushed to runtime because the data structure demanded shared mutable ownership the type system could not express any other way.

use std::rc::Rc;
use std::cell::RefCell;

type NodeRef = Rc<RefCell<Node>>;

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

This compiles and runs. It also reintroduces the exact runtime borrow-checking that Rust’s whole design philosophy is built to avoid at compile time, plus the overhead of reference counting and the very real possibility of creating a reference cycle between next and prev that the reference counter never sees as droppable, a genuine memory leak in a language whose entire selling point is that you should not be able to leak memory in safe code.

What this is actually teaching us

A linked list is basically the worst case for Rust’s ownership model. The classic pointer-chasing form assumes a memory model where any piece of data can have an arbitrary number of references pointing at it from anywhere, with no single owner responsible for cleaning it up. That model is exactly what garbage-collected languages are built around, and it is exactly what Rust’s ownership system replaces with something stricter and, for most data, dramatically faster and safer.

This is also why production Rust code rarely uses linked lists. The standard library’s LinkedList<T> exists, implemented with unsafe code under the hood doing the raw pointer manipulation that safe Rust will not let you do directly, and the standard library's own documentation recommends Vec<T> instead for almost every use case where you would reach for a linked list in another language. Contiguous, growable arrays fit Rust's ownership model naturally, because each element has exactly one owner, the Vec itself, and there is no ambiguity about who is responsible for what.

That afternoon fighting a linked list isn’t wasted time. It is the fastest possible demonstration of what “single owner” actually means in practice, because the alternative data structures you eventually reach for or at least i reached for, Vec, slices, arenas with indices instead of pointers, all exist specifically because they solve the same problems linked lists solve without fighting the ownership model. Once you understand exactly why the linked list resists Rust, the rest of Rust's standard collections stop looking like arbitrary API choices and start looking like the only structures that could have worked given the constraints.

If ownership and the borrow checker are the parts of Rust you keep circling back to, the field guide builds the mental model from the ground up before you ever touch a linked list.

$7 — Zero to Rust: A Systems Programmer’s Field Guide You can read the free sample here — Free 20-page sample