Singly Linked List in Rust

Let’s build a singly linked list in Rust. But first, we need to understand what a linked list is.

A linked list is a data structure made of separate pieces called nodes.

Each node usually stores:

Data — the actual value.
A link/pointer — tells you where the next node is.

For example:

head → 12 → 7 → 31 → null

Unlike an array, linked-list elements do not need to be stored next to each other in memory. This makes operations such as inserting or removing a node at the front very cheap, but accessing a specific element is slower because you usually have to follow the links from the beginning.

A simple node might look like this in Rust:

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

We can create a type alias called Link<T> for Option<Box<Node<T>>>:

type Link<T> = Option<Box<Node<T>>>;

Now, we can write Node<T> as:

struct Node<T> {
    value: T,
    next: Link<T>,
}

And now the linked list itself:

struct LinkedList<T> {
    head: Link<T>,
}

Let’s break down what this code is doing. We have a LinkedList<T>, which is generic over some type T. It contains a single field, head, whose type is Link<T>.

Link<T> is simply a type alias for Option<Box<Node<T>>>. In other words, the head of the list can either be Some, containing a boxed Node<T>, or None, representing an empty list. This structure matches the graphic shown above.

You might be wondering why we need Box here. Why can’t we simply use Option<Node<T>>? The reason is that doing so would make Node<T> recursively contain itself directly, giving it an infinitely large size. Box solves this by introducing a fixed-size pointer between nodes. The next Node<T> is stored in a separate heap allocation, so each Node<T> itself has a finite, compile-time-known size.

Next, we can move to the impl block of the linked list. For now, we’ll just add the new method, which will act as a constructor for the linked list. And initially, the linked list will be empty, which means it will have no nodes, and the head will just be None.

impl<T> LinkedList<T> {
    fn new() -> Self {
        Self { head: None }
    }
}

We can instantiate the linked list as follows:

let mut list = LinkedList::new();

We now have a linked list but it doesn’t do much at the moment. Let’s change that by adding a push_front method that inserts a value at the front of the list.

impl<T> LinkedList<T> {
    ...

    fn push_front(&mut self, value: T) {
        let new_node = Box::new(Node {
            value,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }
}

The push_front method inserts a new value at the beginning of the linked list. It takes a mutable reference to the list and a value of type T.

First, we create a new Node containing the given value. Its next field is set to the current head of the list using self.head.take(). The take method moves the existing value out of head and leaves None in its place.

We then wrap the new node in a Box and assign it to self.head as Some(new_node). This makes the new node the head of the list, while its next pointer refers to what was previously the first node.

Now that we have push_front, we can start adding values to the list:

list.push_front(31);
list.push_front(7);
list.push_front(12);

Because each value is inserted at the front, the list ends up in reverse of the order in which the values were pushed: 12 -> 7 -> 31.

Let’s take a detour and implement the Display trait for LinkedList<T> so that we can print it in a visually intuitive manner on the terminal.

use std::fmt;

impl<T: fmt::Display> fmt::Display for LinkedList<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut current = self.head.as_deref();

        write!(f, "[")?;

        while let Some(node) = current {
            write!(f, "{}", node.value)?;

            current = node.next.as_deref();

            if current.is_some() {
                write!(f, " -> ")?;
            }
        }

        write!(f, "]")
    }
}

We start at the head of the list using as_deref(), which converts the optional boxed node into an optional reference to a Node. We then walk through the list one node at a time.

For each node, we print its value and move to the next node. If another node follows, we print -> between the values. Finally, we wrap the entire output in square brackets.

Now if we do println!("{list}");, it would be displayed as:

[12 -> 7 -> 31]

To remove a value from the front of the list, we can add a pop_front method. Since the list might be empty, the method returns an Option<T>:

impl<T> LinkedList<T> {
    ...

    fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.value
        })
    }
}

We first call self.head.take(), which removes the current head and leaves None in its place. If a head node exists, map gives us ownership of that node. We then update self.head to point to the node’s next value and return the removed node’s value.

If the list is empty, take() returns None, so pop_front simply returns None.

We can test pop_front by removing the first element and then printing the list:

list.pop_front();
println!("{list}");

If the list was previously:

[12 -> 7 -> 31]

then pop_front() removes 12, leaving:

[7 -> 31]

We can also add two small but useful helper methods: peek and is_empty.

fn peek(&self) -> Option<&T> {
    self.head.as_ref().map(|node| &node.value)
}

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

The peek method lets us look at the value at the front of the list without removing it. It returns an Option<&T>, so we get a reference to the value if the list has a head node, or None if the list is empty.

The is_empty method simply checks whether head is None, returning true when the list contains no elements and false otherwise.

Here’s the complete code:

use std::fmt;

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    value: T,
    next: Link<T>,
}

struct LinkedList<T> {
    head: Link<T>,
}

impl<T> LinkedList<T> {
    fn new() -> Self {
        Self { head: None }
    }

    fn push_front(&mut self, value: T) {
        let new_node = Box::new(Node {
            value,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

    fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.value
        })
    }

    fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.value)
    }

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

impl<T: fmt::Display> fmt::Display for LinkedList<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut current = self.head.as_deref();

        write!(f, "[")?;

        while let Some(node) = current {
            write!(f, "{}", node.value)?;

            current = node.next.as_deref();

            if current.is_some() {
                write!(f, " -> ")?;
            }
        }

        write!(f, "]")
    }
}

fn main() {
    let mut list = LinkedList::new();

    list.push_front(31);
    list.push_front(7);
    list.push_front(12);
    println!("{list}");

    list.pop_front();
    println!("{list}");

    println!("Peeking...");
    match list.peek() {
        Some(value) => println!("Head: {value}"),
        None => (),
    }

    while !list.is_empty() {
        list.pop_front();
    }

    println!("Is empty? {}", list.is_empty());
}

Here’s the output:

$ cargo run -q
[12 -> 7 -> 31]
[7 -> 31]
Peeking...
Head: 7
Is empty? true