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.
Top comments (6)
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, usestd::collections::LinkedList(unless for some really weird reason you need a singly-linked list, then build it on yourself).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 ).
Nice article.
By the way instead of creating custom enum "address" Option could be used I think
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
rusticI believe.myList::append is recursive? Could you use while instead or it does not matter? Tail optimization?
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.