Linked List With Rust

March 9, 2025

Linked lists are part of the most basic data structures in Computer Science. They have several advantages over arrays (Skiena, 2020):

Overflow never occurs, unless the memory is actually full
Insertion and deletion are simpler
With large records, moving pointers is easier and faster

These structures use pointers to connect all the pieces in the list by giving a memory address to each item.

As a beginner in Rust, implementing a singly linked list is an opportunity to learn about dynamic memory and ownership. A crucial concept in dynamic memory is the heap: we don’t know the amount of items in the list, so this structure cannot exist in the stack memory. As each item has at most one pointer referring to it, we have unique ownership.

Implementation

Source code

The starting point is defining a node, allowing to contain an integer and a pointer to the next item.

It’s recommended to use smart pointers instead of raw ones. In this case I will use a Box, which allows to reference an item by only one node. With Option is possible to create a nullable pointer.

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

impl Node {
    pub fn new(value: i32) -> Self {
        Self { value, next: None }
    }
}

Now we can create a structure for the linked list.

struct LinkedList {
    head: Option<Box<Node>>,
}

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

`push_front`

The easiest method is inserting at the beginning of the list. If the list is empty, the Box::take does not throw any exception so we can omit that validation.

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

`push_back`

current contains a mutable reference used for traversal. When getting to the last reference in the list (a None node) is where I learned something interesting: compared with C++, you can have a null reference. Since this reference can be manipulated, it’s possible to attach a new element.

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

    while let Some(node) = current {
        current = &mut node.next;
    }

    *current = Some(Box::new(Node::new(value)));
}

`pop_back`

To remove the last element is important to keep track of the second to last node. Deletion occurs detaching the next of that node with Box::take.

fn pop_back(&mut self) -> Option<Node> {
    let mut current = &mut self.head;

    loop {
        if current.is_none() {
            return None;
        }
        if let Some(node) = current {
            if node.next.is_none() {
                let val = node.value;
                *current = node.next.take(); // node.next.take() will return None
                return Some(Node::new(val));
            }
        }
        if let Some(node) = current {
            current = &mut node.next;
        }
    }
}

Pattern matching is one mechanism that help us write elegant and simpler code. Let’s see another version using match:

fn pop_back(&mut self) -> Option<Node> {
    let mut current = &mut self.head;

    loop {
        match current {
            None => return None,
            Some(node) if node.next.is_none() => {
                let val = node.value;
                *current = node.next.take(); 
                return Some(Node::new(val));
            }
            Some(node) => current = &mut node.next,
        }
    }
}

`pop_front`

What I learned here is that in a match, you can use ref mut to change the ownership level and make it broader. self.head in the match pattern is immutable but in one of the branches I could choose otherwise. This is possible because the branches are independent.

fn pop_front(&mut self) -> Option<Node> {
    match self.head {
        None => None,
        Some(ref mut node) => {
            let val = node.value;
            self.head = node.next.take();
            Some(Node::new(val))
        }
    }
}

Testing

Finally, to check that our code is working I implemented some tests. In LinkedList I added to_vec function to help checking the data.

impl LinkedList {
    fn to_vec(self) -> Vec<i32> {
        let mut values: Vec<i32> = Vec::new();
        let mut current = &self.head;

        while let Some(node) = current {
            values.push(node.value);
            current = &node.next;
        }
        values
    }
}

#[test]
fn test_push_back() {
    let mut list = LinkedList::new();

    list.push_back(4);
    list.push_back(5);
    list.push_back(5);
    list.push_back(6);
    assert_eq!(list.to_vec(), vec![4, 5, 5, 6]);
}

#[test]
fn test_push_front() {
    let mut list = LinkedList::new();

    list.push_front(4);
    list.push_front(5);
    list.push_front(5);
    list.push_front(6);
    assert_eq!(list.to_vec(), vec![6, 5, 5, 4]);
}

#[test]
fn test_pop_back_empty() {
    let mut list = LinkedList::new();

    list.pop_back();

    assert_eq!(list.to_vec(), vec![]);
}

#[test]
fn test_pop_back_one_item() {
    let mut list = LinkedList::new();

    list.push_back(4);
    list.pop_back();

    assert_eq!(list.to_vec(), vec![]);
}

#[test]
fn test_pop_back_two_items() {
    let mut list = LinkedList::new();

    list.push_back(4);
    list.push_back(5);
    let popped = list.pop_back();

    assert_eq!(list.to_vec(), vec![4]);
    match popped {
        None => assert!(false),
        Some(node) => assert_eq!(node.value, 5),
    }
}

#[test]
fn test_pop_front_empty() {
    let mut list = LinkedList::new();

    list.pop_front();

    assert_eq!(list.to_vec(), vec![]);
}

#[test]
fn test_pop_front_one_item() {
    let mut list = LinkedList::new();

    list.push_front(4);
    list.pop_front();

    assert_eq!(list.to_vec(), vec![]);
}

#[test]
fn test_pop_front_two_items() {
    let mut list = LinkedList::new();

    list.push_front(4);
    list.push_front(5);
    let popped = list.pop_front();

    assert_eq!(list.to_vec(), vec![4]);
    match popped {
        None => assert!(false),
        Some(node) => assert_eq!(node.value, 5),
    }
}

Conclusion

Probably ownership is one of the challenges to tackle when learning Rust and the borrow checker is one of the most powerful features because forces you to write robust and safer code. When the code compiles, there is a good chance that the code also works. The idea of no having (or reduce considerably) race conditions or undefined behavior in compilation time is amazing and that’s why writing Rust is more difficult than other languages.

References

Skiena, S. S. (2020). The algorithm design manual (3rd ed.). Springer.

The Rust Project Developers. What is ownership? The Rust Programming Language. Retrieved March 9, 2025, from https://doc.rust-lang.org/book/ch04-01-what-is-ownership.html

Rust