Implementation of Linked List in Rust

Introduction

This article will be the start of a series dedicated to data structures and implementation in Rust. I have used this topic as a practical exercise, both to get accustomed to linked lists and to get accustomed to Rust. By no means the algorithm is the best around or optimized, but as long as it is a good thing to understand. We will look first at the idea behind linked list, then look at how to implement it in Rust.

What is a linked list?

The linked list is a data structure (=a way to store data). It is pretty convenient when you always access only the first (or the last) element, or when you have to insert an element somewhere in the middle. Basically you can think of a linked list as some set of objects where each value is stored with a reference to the next one in the list.

One analogy: the scavenger hunt

You can think of building a linked list as organizing a scavenger hunt. Each time the player gets an object, they as well get a hint about where the next object is located. For example, the first hint is: the first object is at the bottom of Eiffel Tower.

Then when you find the object, with it is the next hint: your next object is behind Mona Lisa in the Louvre Museum, etc.

You can see that in this situation you don’t really know how many objects there are overall. But if ever you want to introduce a new game in the middle, you just need to change the corresponding hint. In the example above if I go to the Eiffel Tower and replace the hint by your next object is in the Catacombes, and in the Catacombes I put the hint your next object is behind Mona Lisa in the Louvre Museum, you can see that I don’t need to go to the Louvre or any other location further down the game.

Basic implementation in Rust

The object we are looking at is the following:

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

There are quite a few things to unpack here:

• We use a Box type for the pointer to allow recursive typing
• We use a Option to allow for the null pointer at the end of the list
• We use a Option for the value to allow for a null list.

Let’s build this step by step to understand those Rust complexities. First, we can assume that we store only integers (let’s say i32). So at it simplest the type is the following:

pub struct LinkedList {
    next: Box<LinkedList>,
    val: i32,
}

where Box is a type of reference to help the Rust compiler to allocate enough memory for the data structure. For recursive types like linked list, trees and graphs, this is the easiest option to get the compiler to work. (For more reference, have a look at Smart Pointers).

Looking at the definition above, it doesn’t take into account a few things:

• To which value do we set the next reference for the last element?
• To which value do we set the val initially? (Another way to look at this: what happens after we remove the last value in the list)

We will use the Option Enum for Rust which is designed for those cases.

We end up with the type declared above.

First Feature: Adding an element at the end of the list

 pub fn append(&mut self, new_val: i32) {
        // First case: if the list is empty, we can just set its first element
        if self.val.is_none() {
            self.val = Some(new_val);
            return;
        }
        // If the next element is empty, we just need to point it to a newly created LinkedList
        if self.next.is_none() {
            self.next = Some(Box::new(LinkedList { next: None, val: Some(new_val) }));
            return;
        }
        // Otherwise we just make the recursive call to insert it further down the chain
        self.next.as_mut().unwrap().append(new_val);
    }

A few quick notes:

• Since we modify the linked list, we have to make the self parameter mutable
• We don’t want this function to take ownership of the list, so we need to borrow a reference to the self object
• We need to check at each step if the value or the next are None.

If you want a challenge, try changing the algorithm from recursive to iterative version.