We learned our first data structure "Arrays" in the last article. Now, its time to move on to "Linked Lists". Unlike arrays, linked list data structure allows us to store data without having any kind of index. Another difference is that an array is fixed in size by default. But linked list is always dynamic in size.

Linked list data structure consists of nodes. Each node contains two things, data and a reference to next node's address in memory.

The image above shows how a singly linked list is placed in the memory. But notice how each node is not in a sequential manner like an array. Each node is placed in the memory wherever it can fit in. This gives us a huge advantage over arrays. We can store as many nodes as we want in a linked list.

Another huge advantage of a linked list over an array is that's its faster to insert/delete items from a linked list as compared to an array. Because we don't need to shift the subsequent elements/nodes after inserting anywhere in the middle of linked list.

One drawback of linked list is that its slower than arrays in case of reading a value when its not pointed by head or tail. Because it has to walk up to the node in order to read its data.

Types Of Linked List

There are 3 main types of linked list:

• Singly Linked List

• Doubly Linked List

• Circular Linked List

We will talk about every single one of these, so let's start with Singly Linked List in this article:

Singly Linked List

A singly linked list is the simplest form of linked list. It consists of a number of nodes where each node has some data and a pointer to the next node.

One important thing to know about this form of linked list is that it allows to walk over it in only one direction, head to tail. I mean isn't it obvious? We only got one pointer on each node that references the next node but there is no pointer that references the previous one. So, we only know whats next resulting in one directional traversal.

Let's move on to how we can implement singly linked list in code.

Here are the steps

• Create a node which can store some data and a reference to next node

• Create a List class/struct which will serve the following purposes:

  • allow us to have a reference to head node

  • provide us with methods to push or pop to the linked list

Starting with the node we got:

pub struct Node<T>
{
    data: T,
    next: NodeLink<T>
}

pub type NodeLink<T> = Option<Box<Node<T>>>;

Here we have a generic Node struct with two fields, data and next. Being a generic struct, it will allow us to store any kind of data in this linked list. But the next pointer is a bit complicated.

Rust compiler needs to know the size of next pointer in order to compile it. But if we reference it like next: Option<Node<T>> it will fail to compile because when rust compiler tries to put it on stack, it needs to know the size for Node which can't be determined if it keeps telling rust compiler to get the size of next field from the Node itself recursively.

The fix here is to wrap the it in a Box which has a fixed 8 Byte length on stack. What Box does it stores whatever inside it to the heap and points to it using an 8 Byte pointer in stack.

Finally, we aren't sure if it the last element or not so next field can be empty. We have to use Option<> here so it can be None.

Alright let's create our List struct:

pub struct List<T>
{
    head: NodeLink<T>
}

Notice we got a head field only pointing to the head of the linked list. Where the NodeLink<T> is what we just discussed above.

Alright, now its time to add methods to our linked list so we can create it, then push and pop nodes from it.

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

The new method works like a constructor here. Because of Self return type which refers to the implemented struct itself List<T>, calling it will return a new List of whatever the type hint is provided. So, We can call it like:

let list: List<i32> = List::new();

Push Method

Lets add our first method to push items into the list. Add the following into the implementation block:

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

    self.head = Some(new_node);
}

Let's break it down so we get a better understanding of what is going on here. First we have 2 parameters &mut self and value: T. Why:

• self is a mutable reference because we will be modifying/changing the underlying List<T> object by pushing an item into the list.

• value is generic allow us to push any kind of value.

Now, the first thing we have to do inside the method is to build the new node from given data so we can attach it to the list.

We created the node like:

Node {
    data: value,
    next: self.head.take()
}

It isn't as simple as it look. We got a data field that will simply get the value passed to the method but what is going on with the next field?

Here is the answer. self.head will give us the head which is Option<Box<Node<T>>>, that's simple. But the main thing here is the take() method. It takes the value out from an option and sets None in place of that. So, what it will do here is set the head to None and pass whatever was in the head to next field with a new Option<T> around it. For example,

let mut x = Some(2);
let y = x.take(); // set x to None and y to Option wrapped value of x
assert_eq!(x, None);
assert_eq!(y, Some(2));

Finally we are wrapping this new node into a box so we can have a fixed size pointer in stack.

let new_node = Box::new(Node {
    data: value,
    next: self.head.take()
});

We got the new node ready to be pushed now the last operation is to make it the head of linked list:

self.head = Some(new_node);

Here are the steps we went through in this process:

• We created a new node with its next pointer pointing to the head of linked list and wrapped it in a Box.

• Meanwhile, we also set the head of linked list to None

• Now we simply changed the head to the new node.

At last, we can push something to our list like this:

list.push(35);

Pop Method

Our push method is completed now lets move on to the pop method:

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

        node.data
    })
}

First we got the mutable reference to self again because we are modifying the underlying linked list by popping an item. Then we got the return type of Option<T>, that means it will return the the actual value in the last node on pop operation.

So, what's going on inside this method:

We got self.head.take() again which will set the actual head to None and return the NodeLink which was there. Then we are mapping the NodeLink so we can extract the data inside it.

One thing to notice here is how the map method works. It available on Option enum and it simply allows us to take an Option, apply a function on its value and then return whatever the function returned in a newly wrapped Option. So it basically does Option<T> to Option<U> conversion while giving the full control of what goes inside the output Option.

So, we got applied the map, it will give us Box<Node> in the callback function as the parameter, now we have to do following things in this callback function:

• since its the last element (head) being removed, we have to set the second last element as head

• then we need to return the data of node we just removed

We changed the head to second last element like this:

self.head = node.next;

Now everything is set, all there is left to do is return whatever was just popped out. And for that we will simply return the data of node. Which the map function will wrap in a new Option and return it.

We can pop items from our list like this:

let x = list.pop();

We pop method ends here. Now whats left behind is peek and peek_mut methods because we want to be able to see what is one the head.

Peek Method

What peek method does is let us see what is stored/available in the head of linked list while keeping it read only. Here is the implementation for it:

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

As we don't need to modify/mutate anything in the linked list we we take &self as parameter instead of &mut self. But the interesting thing here is the return type Option<&T>. This means we are returning an option wrapped around the reference of value. So we will always get a Some variant of Option if there is something in the head and None variant if the head isn't pointing to anything. Now, what's going on in the body.

First we have took the head as a ref self.head.as_ref() so we don't consume it. What as_ref does is, it allows us to borrow a reference to the inner value of an Option. So we will get the Option<T> here. But wait, we don't want to return the Box or Node to the user. All this should be abstracted away so we will just return the reference to value inside it. And for the we will use the map method.

Remember, how we used the map method earlier, it will the Option<T>, in our case the Option<&Box<Node>> and provide us with &Box<Node> in the callback function as parameter. We will simply get the reference to the data field from the node. Notice, we are using the dot operator like &node.data, it will auto deref for us so we don't need to worry about anything. Finally, we will have a new Option<&T> with reference to our data in the node.

We can peek into our list like this:

let x = list.peek();

Mutable Peek Method

Now, that we can peek in the linked list, what if we want to change the value. Let's define a similar method as peek but with mutable reference we can can mutate it.

pub fn peek_mut(&mut self) -> Option<&mut T>
{
    self.head.as_mut().map(|node| {
        &mut node.data
    })
}

Yup, its the same as peek method except we are using mutable references. We are using as_mut() method on head instead of as_ref() which still provides the same reference but this time its mutable. While, in the return statement of map method's callback, we are returning &mut instead of & so we will get the desired return type for the peek_mut method which is Option<&mut T>.

Final Code

Here is the final code:

pub struct Node<T>
{
    data: T,
    next: NodeLink<T>
}

pub type NodeLink<T> = Option<Box<Node<T>>>;

pub struct List<T>
{
    head: NodeLink<T>
}

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

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

        self.head = Some(new_node);
    }

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

            node.data
        })
    }

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

    pub fn peek_mut(&mut self) -> Option<&mut T>
    {
        self.head.as_mut().map(|node| {
            &mut node.data
        })
    }
}

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

    #[test]
    fn push_pop() {
        let mut list: List<i32> = List::new();

        list.push(5);
        list.push(9);

        assert_eq!(list.pop(), Some(9));
        assert_eq!(list.pop(), Some(5));
        assert_eq!(list.pop(), None);
    }

    #[test]
    fn peek()
    {
        let mut list: List<i32> = List::new();

        list.push(4);
        list.push(12);

        assert_eq!(list.peek(), Some(&12));
        assert_eq!(list.peek_mut(), Some(&mut 12));

        list.peek_mut().map(|value| {
            *value = 25;
        });

        assert_eq!(list.peek(), Some(&25));
    }
}

Time Complexity

Both push and pop methods in our linked list have a time complexity of O(1) because they directly manipulate the head and no loop is involved. No matter how big the linked list gets, these methods will take O(1) time.

Peek and Mutable Peek methods also have O(1) complexity, because we have a pointer to the head allowing us to peek directly.

Now that Singly Linked List is finished, let's move on to Doubly Linked List!