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.

Implementation

Define an enum for address node

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

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,
}

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))
            }
        }
    }

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

    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);
                }
            }
        }
    }

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.

   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 => {}
            }
        }
    }

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;
    }

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();
}

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

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.