Linked lists in Rust

Picture a treasure hunt. The first clue is in your hand. It does not hold the treasure. It tells you where the next clue is hidden, and that one points to the next, until the last clue shows you the prize. You can only get to clue number 5 by following clues 1 to 4.

That is a linked list. It is a chain. Each item, called a node, holds a value and a link to the next node. The list itself only remembers where the chain starts, which is called the head. To reach any other item, you start at the head and follow the links.

That is the opposite of an array, where the items sit side by side and you can jump straight to any position. In a linked list the items can be anywhere in memory, because each one says where the next is.

Reach for a linked list when most of your work happens at the front of the list, such as adding and removing there, and you never need to read item number 500 directly.

Here is an honest note before we start. In everyday Rust you will almost always use a Vec or a VecDeque instead (lesson 5), because they are simpler and usually faster. So why learn this? Because a linked list is the best small example of how Rust's ownership rules work. Ownership is the rule that every value has exactly one owner, and the value is cleaned up when its owner goes away. A chain of nodes makes you think about that rule in every line, and linked lists are also a very common interview topic.

Remember: in everyday Rust, use a Vec. Learn the linked list to understand ownership.

The picture shows three nodes. head points at the first. Each node holds a value and a link to the next, and the last node's link leads nowhere.

Adding at the front is quick. Make a new node, point it at the old first node, and move head to the new node. Nothing else moves, however long the list is. Removing from the front is the same in reverse. Reading item number 5, though, means following four links from the head, so the cost grows with the position.

Now the Rust part. Rust has no null, the "nothing here" value that many languages use for an empty link. Instead it has Option<T>, which is either Some(value) or None, and the compiler makes you handle both. So "a link to the next node, or no next node" is an Option.

A node also cannot simply contain another node. A Node that held a whole Node inside it would contain another Node, and so on forever, so Rust could never work out its size. The fix is Box<Node>. A Box puts a value on the heap (the large area of memory for values whose size or lifetime is decided while the program runs) and keeps only a small pointer to it. A pointer has a known size, so the problem goes away.

Put together, a link is Option<Box<Node>>: either nothing, or a pointer to the next node, which this node owns. When a node is dropped, the node it owns is dropped too. That is also why a doubly linked list, with links in both directions, is much harder: each node would need two owners, and Rust allows only one. Doing that properly needs shared ownership types that go beyond this lesson.

Here is a list that can push, pop and peek at the front.

/// One link in the chain. It owns its value and owns the next node.
struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

/// A singly linked list. It only knows where the first node is.
pub struct LinkedList {
    head: Option<Box<Node>>,
    len: usize,
}

impl LinkedList {
    pub fn new() -> Self {
        LinkedList { head: None, len: 0 }
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn is_empty(&self) -> bool {
        self.head.is_none()
    }

    /// Adds a value at the front.
    pub fn push_front(&mut self, value: i32) {
        let node = Box::new(Node {
            value,
            next: self.head.take(), // the old first node becomes the second
        });
        self.head = Some(node);
        self.len += 1;
    }

    /// Removes and returns the front value, or `None` if the list is empty.
    pub fn pop_front(&mut self) -> Option<i32> {
        self.head.take().map(|node| {
            self.head = node.next; // the second node becomes the first
            self.len -= 1;
            node.value
        })
    }

    /// Looks at the front value without removing it.
    pub fn peek_front(&self) -> Option<&i32> {
        self.head.as_ref().map(|node| &node.value)
    }
}

impl Default for LinkedList {
    fn default() -> Self {
        Self::new()
    }
}

Go through it in order.

• struct Node has a value and a next link. LinkedList holds the head link and a count, len.
• push_front builds a new Box<Node> whose next is the old head, then makes the new node the head. The old head has to be moved into the new node, and that is what self.head.take() does.
• pop_front does the reverse. It takes the head out, makes the second node the new head, and hands back the value.
• peek_front returns Option<&i32>, a borrowed look at the value. as_ref() turns the Option<Box<Node>> into an Option of a reference, so the head is looked at but not moved.

let mut slot = Some(5);
let taken = slot.take(); // moves the value out, leaves `None` behind

assert_eq!(taken, Some(5));
assert_eq!(slot, None);

Without take, the push_front method would not compile, and the error message about moving out of borrowed content is one every Rust learner meets.

Remember: when you need to move a value out of a field you only borrow, use take() and leave None behind.

Now adding at the back. The list only knows its head, so it has to walk to the last node.

impl LinkedList {
    /// Adds a value at the back by walking to the empty slot after the last node.
    pub fn push_back(&mut self, value: i32) {
        let mut cursor = &mut self.head;
        while let Some(node) = cursor {
            cursor = &mut node.next;
        }
        *cursor = Some(Box::new(Node { value, next: None }));
        self.len += 1;
    }
}

cursor is a mutable reference to a link. It starts at self.head. While the link holds a node, the loop moves the cursor to that node's next link. When the loop stops, cursor points at the empty link after the last node, and *cursor = Some(...) fills it. Notice that the walk makes this O(n). Keeping a second pointer to the tail would make it quick, but two pointers into the same chain is exactly what Rust's rules push back on, and it is why this is the hard case.

To look at every value without removing any, the list needs an iterator, which is a small object that hands out items one at a time.

/// Walks the list from the front, lending out one value at a time.
pub struct Iter<'a> {
    next: Option<&'a Node>,
}

impl LinkedList {
    pub fn iter(&self) -> Iter<'_> {
        Iter {
            next: self.head.as_deref(),
        }
    }
}

impl<'a> Iterator for Iter<'a> {
    type Item = &'a i32;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_deref();
            &node.value
        })
    }
}

Iter<'a> holds a reference to the next node. The 'a is a lifetime: a label that says how long a borrow lasts. Here it says the iterator cannot outlive the list it is looking into, which stops you from changing or dropping the list while you are halfway through reading it. The as_deref() call turns an Option<Box<Node>> into an Option<&Node>, so the iterator borrows each node instead of taking it.

One last piece. When a list is dropped, Rust drops the head, which drops the node it owns, and so on down the chain. For a very long list that chain of drops is as deep as the list is long, and it can overflow the stack (the limited area of memory used to keep track of function calls). So a careful list frees its nodes in a loop:

impl Drop for LinkedList {
    /// Frees the nodes one at a time. The automatic version frees the first
    /// node, which frees the second, and so on, so a long list could overflow
    /// the stack.
    fn drop(&mut self) {
        let mut current = self.head.take();
        while let Some(mut node) = current {
            current = node.next.take();
        }
    }
}

Each pass takes one node, detaches its next, and lets the node go. The chain never goes deep.

The standard library does have a linked list, and unlike ours it links in both directions.

use std::collections::LinkedList;

let mut list = LinkedList::new();
list.push_back(2);
list.push_back(3);
list.push_front(1);

assert_eq!(list.front(), Some(&1));
assert_eq!(list.pop_back(), Some(3));
assert_eq!(list.len(), 2);

You will almost never need it. Its own documentation points readers to Vec or VecDeque for most uses. The reason is how computers read memory. A processor keeps a small, very fast store called a cache, and it loads memory into the cache in chunks. A Vec keeps its items next to each other, so one chunk brings in many items. A linked list's nodes are scattered, so following each link can mean going back to slow memory. A list wins only in special cases, such as when you must keep a hold on a node while other nodes are added and removed around it.

The row to remember is reading by position. On a Vec it is O(1), and here it is O(i). Linked lists trade that away for cheap changes at one end, and in practice a Vec is quick enough that the trade rarely pays off.

These three use a node type with public fields, so that you can build a list and check the result. from_slice builds a list from a slice, and to_vec reads one back. Open the Playground link to get all of this with each problem.

/// A node for the practice problems. Its fields are public so a test can
/// build and inspect lists.
#[derive(Debug, PartialEq, Eq)]
pub struct ListNode {
    pub value: i32,
    pub next: Option<Box<ListNode>>,
}

/// Builds a list from a slice, in the same order.
pub fn from_slice(values: &[i32]) -> Option<Box<ListNode>> {
    let mut head = None;
    for &value in values.iter().rev() {
        head = Some(Box::new(ListNode { value, next: head }));
    }
    head
}

/// Reads a list back into a `Vec`, to compare in a test.
pub fn to_vec(head: &Option<Box<ListNode>>) -> Vec<i32> {
    let mut out = Vec::new();
    let mut current = head;
    while let Some(node) = current {
        out.push(node.value);
        current = &node.next;
    }
    out
}

Two of the problems take the list by value, which means they get ownership of the nodes and may re-link them freely. middle only borrows the list, because it just reads it.

pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    todo!("turn every next pointer around")
}

pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut reversed = None; // the finished part, built back to front
    let mut rest = head; // the part not yet visited
    while let Some(mut node) = rest {
        rest = node.next.take(); // cut this node off from the rest
        node.next = reversed; // point it at the finished part
        reversed = Some(node); // it becomes the new front
    }
    reversed
}

pub fn middle(head: &Option<Box<ListNode>>) -> Option<i32> {
    todo!("find the middle value; for two middles, take the second")
}

pub fn middle(head: &Option<Box<ListNode>>) -> Option<i32> {
    let mut slow = head.as_ref();
    let mut fast = head.as_ref();
    while let Some(ahead) = fast {
        let Some(two_on) = ahead.next.as_ref() else {
            break;
        };
        fast = two_on.next.as_ref();
        slow = slow.and_then(|node| node.next.as_ref());
    }
    slow.map(|node| node.value)
}

pub fn merge_sorted(
    a: Option<Box<ListNode>>,
    b: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    todo!("join two sorted lists into one sorted list")
}

pub fn merge_sorted(
    a: Option<Box<ListNode>>,
    b: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    let (mut a, mut b) = (a, b);
    let mut head = None;
    let mut tail = &mut head; // the empty slot where the next node goes

    while let (Some(x), Some(y)) = (&a, &b) {
        let source = if x.value <= y.value { &mut a } else { &mut b };
        let mut node = source.take().expect("just checked it is Some");
        *source = node.next.take(); // the source moves on to its next node
        tail = &mut tail.insert(node).next; // append, then point at the new empty slot
    }
    *tail = a.or(b); // at most one list still has nodes: attach it whole
    head
}

Linked list questions are a classic because they test careful handling of links rather than clever maths. A few habits help.

• Draw it first. Sketch the nodes and arrows, and move one arrow at a time. Most mistakes are an arrow changed too early, which loses the rest of the list.
• Know the standard patterns. Reversing a list (problem 1), two walkers at different speeds (problem 2), and merging with a tail pointer (problem 3) come up again and again. Two other familiar questions are removing the nth node from the end, and detecting a cycle, where a chain loops back on itself. Safe Rust's Box lists cannot form a cycle, but the questions are asked in other languages, and the fast and slow walkers are how they are solved.
• Check the edges. An empty list, a list of one node, and removing or changing the head are where answers usually break.
• Say the cost. "One pass, so O(n) time, and I only re-link, so O(1) extra space" is a complete answer.
• In Rust, say why the types look like they do. Explaining that Option<Box<Node>> means "maybe a node, which I own", and that you use take() to move a link out without leaving a hole, shows you understand ownership, not just syntax.
• Know when not to use a list. Saying that you would reach for a Vec or a VecDeque in real code, and why, is a strong answer.

Made by VeraStack Labs