Rust Singly Linked List Implementation

Singly Linked List is a fundamental data structure that every developer should implement in Rust. It’s simple enough to be implemented in several lines of code in C++ based languages but has some challenges in Rust implementation. This article will teach you to implement your own Singly Linked List.

General idea

First of all, let’s discuss the main idea of this data structure.

The Linked List is a linear data structure, similar to arrays. Arrays have some limitations, such as fixed size and expensive insertion. Linked List is designed to overcome these limitations.

The main advantage of Singly Linked List is simplicity in implementation and dynamic size.

Representation

Singly Linked List is represented as follows:

Every item is called as Node.
It contains the value itself and a pointer to the next item.
If there are no more items, the last node will contain a pointer to NULL or dumb value.
The first node is called HEAD. HEAD can be NULL or dumb value representing an empty Linked List.

Singly Linked List

To insert an item into the list, we should create a Node with a value equal to item and a next pointer pointing to HEAD. Then we should replace HEAD with the newly created Node.

Add new node in Singly Linked List

To pop an item, we can replace the HEAD with the next pointer and return the previous value pointer by HEAD.

List Node Implementation

We should store every node in the heap as we are working with pointers. This way, we will keep only metadata on the stack.

Let’s start with the ListNode implementation. It’s an enum that can be Empty (dumb value instead of NULL in other languages) or NonEmpty and contains some value. The value will be stored in the ListNodeValue struct together with the next pointer.

struct ListNodeValue<T> {
    item: T,
    next: Box<ListNode<T>>,
}

impl<T> ListNodeValue<T> {
    fn new(item: T, next: Box<ListNode<T>>) -> Self {
        Self { item, next }
    }
}

enum ListNode<T> {
    Empty,
    NonEmpty(ListNodeValue<T>),
}

impl<T> ListNode<T> {
    fn new(item: T, next: Box<ListNode<T>>) -> Self {
        ListNode::NonEmpty(ListNodeValue::new(item, next))
    }

    fn take(&mut self) -> Self {
        let mut cur = Self::Empty;
        std::mem::swap(&mut cur, self);
        cur
    }
}

You can see that next is Box<ListNode<T>>. It means that we are storing a single reference to the heap which contains ListNode<T>. Again, that node can be Empty or NonEmpty.

The most interesting method here is take. The implementation is the same as in the Option enum. We are swapping the current value with Empty and returning it. It will be usefull later.

Singly Linked List Implementation

Next, we should create a public struct SinglyLinkedList which will contain methods push, pop, and len.

pub struct SinglyLinkedList<T> {
    head: Box<ListNode<T>>,
    size: usize,
}

impl<T> SinglyLinkedList<T> {
    pub fn new() -> Self {
        Self {
            head: Box::new(ListNode::Empty),
            size: 0,
        }
    }

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

This struct contains two fields: head and size. size will count the number of nodes to implement the len() method. head is a pointer to the heap that contains ListNode. By default, this node is empty.

Push method

Have a look at the push method.

pub fn push(&mut self, item: T) {
    let cur_head = self.head.take();
    let new_node = Box::new(ListNode::new(item, Box::new(cur_head)));

    self.head = new_node;
    self.size += 1;
}

It creates a new node, puts item inside, and points next to the current head value. Borrow checker will not allow you to borrow head and then reassign it. To trick the compiler, I am using the take method mentioned before, creating a new node with that value and assigning it to the head. And don’t forget to increase the size of the List after all.

Pop method

Now investigate the pop method:

pub fn pop(&mut self) -> Option<T> {
    let node = self.head.take();

    if let ListNode::NonEmpty(node) = node {
        self.head = node.next;
        self.size -= 1;
        Some(node.item)
    } else {
        None
    }
}

Again, we take the current value out of head and check it. We should return None, because our list is empty. Otherwise, we should decrease the size by one, repoint head to the next node and return the current node value.

Testing

This collection is almost done. Let’s start writing some tests to verify it.

#[cfg(test)]
mod tests {
    use super::SinglyLinkedList;

    #[test]
    fn it_works() {
        let mut linked_list: SinglyLinkedList<usize> = SinglyLinkedList::new();
        for i in 1..=10 {
            linked_list.push(i);
        }

        for i in (1..=10).rev() {
            let cur = linked_list.pop();
            assert_eq!(Some(i), cur);
        }

        assert_eq!(None, linked_list.pop());
    }

    #[test]
    fn test_series_of_pops_and_inserts() {
        let mut list: SinglyLinkedList<usize> = SinglyLinkedList::new();
        assert_eq!(list.pop(), None);

        list.push(3);
        list.push(42);
        assert_eq!(list.pop(), Some(42));
        assert_eq!(list.len(), 1);

        list.push(93);
        assert_eq!(list.len(), 2);
        assert_eq!(list.pop(), Some(93));
        assert_eq!(list.pop(), Some(3));
        assert_eq!(list.pop(), None);
        assert_eq!(list.len(), 0);

        list.push(20);
        assert_eq!(list.pop(), Some(20));
        assert_eq!(list.pop(), None);
    }
}

Adding additional traits implementations

Now we are confident that everything works fine. We can enhance this collection by implementing common traits such as Debug, Clone, and Iterator. Derive macro can implement most of them, except for Clone and Iterator, which are implemented as follows:

impl<T> Clone for ListNodeValue<T>
where
    T: Clone,
{
    fn clone(&self) -> Self {
        Self {
            item: self.item.clone(),
            next: Box::clone(&self.next),
        }
    }
}

impl<T> Iterator for SinglyLinkedList<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.pop()
    }
}

Iterator trait is easy to implement. However, the Clone trait is tricky. We can clone only when generic argument T is Clone. Therefore, we should restrict T by using the where T: Clone clause.

Bonus

Do you know the standard library’s vec![] macro? We can implement our declarative macro for the SinglyLinkedList. Here it is:

#[macro_export]
macro_rules! slist {
    () => {SinglyLinkedList::new()};
    ($($element:expr,)*) => {{
        let mut list = SinglyLinkedList::new();
        $(
            {
                list.push($element);
            }
        )*
        list
    }};
    ($($element:expr),*) => {{
        slist!($($element,)*)
    }};
}

Declarative macros are similar to match statements in Rust. This macro has three arms.

The first arm checks the case when no item is added slist![]. It’s implemented by simply returning the SinglyLinkedList.
The second arm checks the case when we have a list of items delimited by the comma. For example: slist![1, 2, 3,], slist![1,]. The implementation is simple: we create a list and add items one by one. In the end, we return that List.
The last arm is created for convenience. It allows specifying items with no tailing comma: slist![1, 2, 3], slist![1]. It calls the previous implementation by adding the trailing comma.

You can add an arm to match the case slist![5; 100], which should push one hundred 5 to the list. I leave it as a task for you.

Final code

We should test all the code and trait implementations to verify it’s working correctly. The final implementation will look like this. You can view the final code in my public repo.

#[derive(Debug, PartialEq)]
struct ListNodeValue<T> {
    item: T,
    next: Box<ListNode<T>>,
}

impl<T> ListNodeValue<T> {
    fn new(item: T, next: Box<ListNode<T>>) -> Self {
        Self { item, next }
    }
}

impl<T> Clone for ListNodeValue<T>
where
    T: Clone,
{
    fn clone(&self) -> Self {
        Self {
            item: self.item.clone(),
            next: Box::clone(&self.next),
        }
    }
}

#[derive(Debug, Clone, PartialEq)]
enum ListNode<T> {
    Empty,
    NonEmpty(ListNodeValue<T>),
}

impl<T> Default for ListNode<T> {
    fn default() -> Self {
        Self::Empty
    }
}

impl<T> ListNode<T> {
    fn new(item: T, next: Box<ListNode<T>>) -> Self {
        Self::NonEmpty(ListNodeValue::new(item, next))
    }

    fn take(&mut self) -> Self {
        let mut cur = Self::Empty;
        std::mem::swap(&mut cur, self);
        cur
    }
}

#[derive(Debug, Default, Clone, PartialEq)]
pub struct SinglyLinkedList<T> {
    head: Box<ListNode<T>>,
    size: usize,
}

impl<T> SinglyLinkedList<T> {
    pub fn new() -> Self {
        Self {
            head: Box::new(ListNode::Empty),
            size: 0,
        }
    }

    pub fn push(&mut self, item: T) {
        let cur_head = self.head.take();
        let new_node = Box::new(ListNode::new(item, Box::new(cur_head)));

        self.head = new_node;
        self.size += 1;
    }

    pub fn pop(&mut self) -> Option<T> {
        let node = self.head.take();

        if let ListNode::NonEmpty(node) = node {
            self.head = node.next;
            self.size -= 1;
            Some(node.item)
        } else {
            None
        }
    }

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

impl<T> Iterator for SinglyLinkedList<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.pop()
    }
}

#[macro_export]
macro_rules! slist {
    () => {SinglyLinkedList::new()};
    ($($element:expr,)*) => {{
        let mut list = SinglyLinkedList::new();
        $(
            {
                list.push($element);
            }
        )*
        list
    }};
    ($($element:expr),*) => {{
        slist!($($element,)*)
    }};
}

#[cfg(test)]
mod tests {
    use super::SinglyLinkedList;

    #[test]
    fn it_works() {
        let mut linked_list: SinglyLinkedList<usize> = SinglyLinkedList::new();
        for i in 1..=10 {
            linked_list.push(i);
        }

        for i in (1..=10).rev() {
            let cur = linked_list.pop();
            assert_eq!(Some(i), cur);
        }

        assert_eq!(None, linked_list.pop());
    }

    #[test]
    fn test_series_of_pops_and_inserts() {
        let mut list: SinglyLinkedList<usize> = SinglyLinkedList::new();
        assert_eq!(list.pop(), None);

        list.push(3);
        list.push(42);
        assert_eq!(list.pop(), Some(42));
        assert_eq!(list.len(), 1);

        list.push(93);
        assert_eq!(list.len(), 2);
        assert_eq!(list.pop(), Some(93));
        assert_eq!(list.pop(), Some(3));
        assert_eq!(list.pop(), None);
        assert_eq!(list.len(), 0);

        list.push(20);
        assert_eq!(list.pop(), Some(20));
        assert_eq!(list.pop(), None);
    }

    #[test]
    fn test_macro_empty() {
        let mut list: SinglyLinkedList<usize> = slist![];
        assert_eq!(list.pop(), None);
    }

    #[test]
    fn test_macro_one() {
        let mut list: SinglyLinkedList<usize> = slist![42];
        assert_eq!(list.pop(), Some(42));
        assert_eq!(list.pop(), None);
    }

    #[test]
    fn test_macro_two() {
        let mut list: SinglyLinkedList<usize> = slist![42, 50];
        assert_eq!(list.pop(), Some(50));
        assert_eq!(list.pop(), Some(42));
        assert_eq!(list.pop(), None);
    }

    #[test]
    fn test_macro_with_comma() {
        let mut list: SinglyLinkedList<usize> = slist![
            42, 50, 1, 10, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
            23, 24, 25, 26, 27, 28, 29, 30,
        ];
        let mut vector = vec![
            42, 50, 1, 10, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
            23, 24, 25, 26, 27, 28, 29, 30,
        ];

        assert_eq!(list.len(), vector.len());
        while let Some(value) = list.pop() {
            assert_eq!(Some(value), vector.pop());
        }

        assert_eq!(list.pop(), None);
        assert_eq!(vector.pop(), None);
    }

    #[test]
    fn test_iter() {
        let list = slist![1, 2, 3, 4, 5];
        let vector: Vec<_> = list.collect();

        assert_eq!(vector, vec![5, 4, 3, 2, 1]);
    }

    #[test]
    fn test_clone() {
        let list = slist![1, 2, 3, 4, 5];
        let cloned = list.clone();

        assert_eq!(list.len(), 5);
        assert_eq!(list, cloned);
    }
}

General idea#

Representation#

List Node Implementation#

Singly Linked List Implementation#

Push method#

Pop method#

Testing#

Adding additional traits implementations#

Bonus#

Final code#