DEV Community

loading...
Cover image for Implementing Linked List in Rust

Implementing Linked List in Rust

felixfaisal
Linux Foundation Mentee @FD.io | MLH Fellow'21 | FOSSEE Fellow'20 | Open Source Contributor
・3 min read

Linked List is one of the most known data structures implemented in every language. It is used to build data structures on top of it such as stack or queue etc. It is difficult to implement Linked List in Rust as what is allowed in most languages is simply not allowed in Rust, While it may seem to be a little difficult but the Rust compiler also at the same time makes sure that your code is memory safe.

Linked List

A linked list is a collection of nodes connected to each other via pointers. It is stored on the heap as it allows it to grow or shrink when the program is being executed.

Linked List

Implementation

Define an enum for address node

#[derive(Clone)]
enum address {
    address(Box<myList>),
    Nil,
}
Enter fullscreen mode Exit fullscreen mode

The reason why I'm choosing to use an Enum for address is because Rust doesn't provide Null types so suppose there is only one element in the Linked list then it is supposed to have a null address. This can also be solved by using Option but I'm using an Enum instead.

Define List Structure

#[derive(Clone)]
struct myList {
    value: u32,
    next: address,
}
Enter fullscreen mode Exit fullscreen mode

CRUD Methods for Linked List

impl myList {
    fn append(&mut self, elem: u32) {
        match self.next {
            address::address(ref mut next_address) => {
                next_address.append(elem);
            }
            address::Nil => {
                let node = myList {
                    value: elem,
                    next: address::Nil,
                };
                self.next = address::address(Box::new(node))
            }
        }
    }
Enter fullscreen mode Exit fullscreen mode

This creates a new node and appends it to the end of the list.
Append

    fn delete(&mut self, elem: u32) {
        match self.next {
            address::address(ref mut next_address) => {
                if next_address.value == elem {
                    println!("Deleting value {}", next_address.value);
                    self.next = next_address.next.clone();
                } else {
                    next_address.delete(elem);
                }
            }
            address::Nil => {
                if self.value == elem {
                    self.value = 0;
                } else {
                    println!("Element {} does not exist in the linked list", elem);
                }
            }
        }
    }
Enter fullscreen mode Exit fullscreen mode

This function first finds the elements to delete then deletes it by changing the address of its previous node to the address of its next node. However, this implementation doesn't check if the head node has the element or not.

Delete

   fn count(&self) -> u32 {
        match self.next {
            address::address(ref newaddress) => 1 + newaddress.count(),
            address::Nil => 0,
        }
    }
 fn list(&self) {
        if self.value == 0 {
            println!("The list is empty")
        } else {
            println!("{}", self.value);
            match self.next {
                address::address(ref next_address) => next_address.list(),
                address::Nil => {}
            }
        }
    }
Enter fullscreen mode Exit fullscreen mode

The count function counts the number of elements present in the linked list and the list function prints all the elements present in the array. Both of these functions are implemented recursively.

Lastly, We have the update function which takes in the position and the element that needs to be updated, This function is implemented iteratively.

fn update(&mut self, index: u32, elem: u32) {
        let mut i = 0;
        let mut j = self;
        if i == index {
            j.value = elem;
        }
        while i < index {
            // println!("{}", j.value);
            match j.next {
                address::address(ref mut next_address) => j = next_address,
                address::Nil => {}
            }
            i = i + 1;
        }
        j.value = elem;
    }
Enter fullscreen mode Exit fullscreen mode

Now let's have a look at our main function

fn main() {
    let mut head = myList {
        value: 8,
        next: address::Nil,
    };
    head.append(9);
    head.append(10);
    head.append(11);
    head.list();
    println!("The size of the list is {}", head.count());
    head.update(4, 20);
    head.update(0, 6);
    head.list();
}
Enter fullscreen mode Exit fullscreen mode

We first define the head element and then perform the following CRUD operations, Let us see what output we get when we perform cargo run

   Finished dev [unoptimized + debuginfo] target(s) in 0.29s
     Running `target/debug/algo`
8
9
10
11
The size of the list is 3
6
9
10
20
Enter fullscreen mode Exit fullscreen mode

This is not a perfect implementation as you can see I've missed out on several edge cases which I'm looking forward to addressing in my next blog. It's an implementation that works really well and I'd encourage you to try it out and make it much better.

Discussion (6)

Collapse
chayimfriedman2 profile image
Chayim Friedman

Implementing linked list is good for learning, but I hope you're not trying to actually use it in productions.

Vecs are much better, and if for some reason you want a linked list, use std::collections::LinkedList (unless for some really weird reason you need a singly-linked list, then build it on yourself).

Collapse
felixfaisal profile image
felixfaisal Author

True, It is essentially made for learning . When developing software I would always prefer using existing libraries than creating my own ( don't reinvent the wheel unless the wheel is square shaped ).

Collapse
vit1251 profile image
Vitold S

myList::append is recursive? Could you use while instead or it does not matter? Tail optimization?

Collapse
felixfaisal profile image
felixfaisal Author

Yeah, It is possible to use a while loop instead of it being recursive, I found it easier to use recursive along with match. There's a lot I haven't accounted for, It was just my first implementation that worked and I wanted to write an article on it.

Collapse
vteremasov profile image
ντξrξμαsον

Nice article.
By the way instead of creating custom enum "address" Option could be used I think

Collapse
felixfaisal profile image
felixfaisal Author

Yeah. I've mentioned it that we could use Option as well. I felt comfortable with enum as a beginner but using an option instead is more rustic I believe.