LESSON 303 OF 414 · LINKED LISTS

Linked Lists in Rust: Option, Box and Ownership

Watch the lesson

In this video lesson we will learn about Linked Lists - how they work, operations we can perform on them and some real-life applications:

Next lesson

RUST · LINKED LISTS

Linked Lists in Rust, explained

What a linked list is

A linked list stores a sequence as a chain of small separate pieces called nodes. Each node holds one value and a link to the next node. The first node is the head, and the last node's link says "nothing follows". To reach any element you start at the head and follow the links one by one.

That differs from a Vec, which keeps its elements side by side in one block of memory and can jump straight to element i. The two structures trade strengths:

Operation	Linked list	`Vec`
Read element at position `i`	O(i), walk from the head	O(1)
Insert or remove at the front	O(1)	O(n), everything shifts
Insert or remove after a node you already hold	O(1), relink two pointers	O(n), everything shifts
Search for a value	O(n)	O(n)

Linked lists are mostly a way to practise thinking about references, and a common subject of interview problems: reverse a list, find the middle, detect a loop, merge two sorted lists.

A node in Rust

In Rust a node is a struct whose link is an Option wrapped around a Box:

struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

Each part has a job:

Option expresses the end of the list. None means no next node, and Some(node) means there is one. Rust has no null pointer, so the type itself forces you to handle the missing case.
Box puts the next node on the heap and stores a pointer to it. It is required: a struct can't contain itself directly, because it would have infinite size. Writing next: Option<ListNode> fails to compile with the error "recursive type `ListNode` has infinite size".

The head of a list is simply an Option<Box<ListNode>>. An empty list is None.

Ownership is the main difference

Each node owns the next one through its Box, so a list is a chain of owners. That has consequences you won't meet in a language with a garbage collector:

To walk the list without changing it, hold a reference to the current link and advance it. Nothing is moved.
To change a link, you can't just overwrite it while another variable still owns what it pointed to. The method Option::take() moves the value out and leaves None in its place, which makes relinking safe.
When you hand a head to a function by value, the caller loses it. The function must give a list back, usually the new head.

Core operations

This program builds a list at the front, prints it, inserts after the first node and reverses it:

#[derive(Debug)]
struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

fn push_front(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
    Some(Box::new(ListNode { val, next: head }))
}

fn print_list(head: &Option<Box<ListNode>>) {
    let mut cur = head;
    while let Some(node) = cur {
        print!("{} -> ", node.val);
        cur = &node.next;
    }
    println!("None");
}

fn reverse(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut prev = None;
    let mut cur = head;
    while let Some(mut node) = cur {
        cur = node.next.take();
        node.next = prev;
        prev = Some(node);
    }
    prev
}

fn insert_after_first(head: &mut Option<Box<ListNode>>, val: i32) {
    if let Some(first) = head {
        let rest = first.next.take();
        first.next = Some(Box::new(ListNode { val, next: rest }));
    }
}

fn main() {
    let mut head = None;
    for v in [3, 2, 1] {
        head = push_front(head, v);
    }
    print_list(&head);
    insert_after_first(&mut head, 10);
    print_list(&head);
    let head = reverse(head);
    print_list(&head);
}

It prints:

1 -> 2 -> 3 -> None
1 -> 10 -> 2 -> 3 -> None
3 -> 2 -> 10 -> 1 -> None

How each function works:

push_front creates a node whose next is the old head and returns it as the new head. It takes constant time, because nothing else moves.
print_list keeps a reference cur to the current link. while let Some(node) = cur runs while there is a node, and cur = &node.next steps forward without taking ownership.
insert_after_first detaches the rest of the list with take(), then creates a new node that points to it and makes it the first node's next. Two links change, and the cost doesn't depend on the list's length.
reverse walks the list once. For each node it detaches the remainder with take(), points the node's next at the part already reversed (prev), and makes the node the new prev. When the loop ends, prev is the old tail, which is the new head. It takes O(n) time and moves the existing nodes without allocating new ones.

Gotchas

Forgetting take(). Trying to move node.next out of a node you only borrow is a compile error, because the node would be left with a hole in it.
Indexing doesn't exist. There is no list[i]. Reaching position i means following i links.
Very long lists and drop. When a boxed list is dropped, the nodes are freed through nested drops. A list of one million nodes overflowed the stack when it went out of scope. For lists of that size, unlink the nodes in a loop before dropping them.
The standard library. Rust has std::collections::LinkedList, but Vec or VecDeque is almost always a better choice in everyday code. Hand-written lists matter for learning and for problems that give you a ListNode.

Key takeaways

A linked list is a chain of nodes, each holding a value and a link to the next, with the head giving access to the whole chain.
In Rust the link is Option<Box<ListNode>>: Option marks the end and Box lets the type refer to itself.
Inserting or removing at a known position is O(1). Reaching a position, or searching, is O(n).
Walk a list with a reference, and relink with take(), so ownership stays clear.
Most list problems come down to careful pointer rewiring, like the loop in reverse.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free