I too made a Singly Linked List on RUST FINALLY!!!

Yes you read the title right and I am going to be explaining about how I implemented my first linked list in rust and also share my learning experience so far with the language.

When I started my rust journey 3 months ago, as anybody would say the learning experience wasn't easy at all and I would agree with the community’s wisdom that “The learning curve is too steep”. Rust is a language that will break you but also it builds you up teaching you the right ways to use all the right tools at your disposal in the right way and trust me when you finally overcome the challenge you will feel like a literal GOD seeing finer things in your code that you would have never bothered to think about and why do we need to right especially when the language handles it internally.

Unlike any language where you can straight up jump into the language without any prior knowledge and slowly learn advanced stuff with experience (trust me I used Java full-time only at my workplace and Python during almost all of my college days), Rust asks you the question why not make you use all the mechanics all the time without stopping. Unlike any languages where you can easily cut corners and write mediocre code that might end up as a complete nightmare during refactoring after the project grows ginormous, Rust makes you write the better code during the development process itself or else it shall not compile. Yes this behavior might sound daunting from an organization standpoint that wants to deliver the code to its customers as fast as possible into the market in order to put up tough fight with its competitors, if we think of this from a developers point of view this is really a blessing in disguise and there’s always a trade-off and this is the price you should be willing to pay for accuracy and less post prod bugs especially due to unsafe pointer usage or bad condition handling. Now if you love accuracy combined with raw unprecedented speed you must give Rust a try, but if quick development and deployment to the market is the goal, Rust is the worst choice to make from an organization standpoint. Enough me rambling about rust and let’s get started on my story of implementing my first Single Linked List and why I loved the pain of implementing it on Rust. Let’s get started.

Yesterday on a friday evening right after completing my organizational responsibilities, I wanted to practise some rust and so I ended up choosing to implement Singly Linked List on Rust. What bad could happen! Anyways fast forwarding a bit on my research about safe practices which was too much to process, I started writing my code to see if I can actually do it my way first with my limited knowledge. So first thing first let’s think about what’s a Linked List and its behavior. It’s just a chain of pointers pointing to a set of data in a certain order isn’t it. One important point to note here is that your linked list is made up of Nodes that in turn contains two variables data and a next pointer. And now if we think of it this next pointer can be either Empty/None or contain another Node. If you are still following this is where we are going to think a bit differently as compared to other languages. So let’s model our thought process up until now and let's get Rusty.

//Our actual linked list

pub struct List{

 ? pub(crate) head: Link

}




//enum to represent the ambiguity of our next node

pub enum Link{

 ? Empty,

 ? More(Box<Node>)

}




//our node struct that will get linked together. Notice that the next dtype is our enum here

pub struct Node{

 ? data: i32,

 ? next: Link

}        

Okay cool we have modeled out data, now let’s concentrate on the behavior of our singly linked list. Here comes the real challenge in our thought process. We are provided three primary weapons in our arsenal namely self, &self and &mut self and they are key to writing a good code in rust. So let’s understand their significance before we dive into the code.?

Self -> hands over the ownership to the function that consumes it. (Mostly not preferable).

&self -> hands over a reference to the data with read only access. (great)

&mut self -> hands over a reference that can mutate with a few sets of rules to regulate the solidity of the final product.

I shall be explaining two functions here for our singly linked list namely push and print and we shall see how we will be implementing it on rust soon.

Push Method

This method shall add the element to the start of our linked list and the code for it is as follows

//Init function for the list

pub fn new() -> Self{

 ? List{ head: Link::Empty }

}




//Here we use mem::replace as a sort of hack to allow such mutation

//Notice &mut self here which is crucial for mutating our self object


pub fn push(&mut self,val:i32){

 ? let new_node = Node{ data: val, next: mem::replace(&mut self.head, Link::Empty) };

 ? self.head = Link::More(Box::new(new_node));

}        

Print Method

This was my favorite one to implement as it showcases the true power of pattern matching in an amazing way without wasting memory on duplicating pointers.

pub fn print(&self, link: &Link){

 ? ? ? match link {

 ? ? ? ? ? Link::Empty => {return;}

 ? ? ? ? ? More(i) => {

 ? ? ? ? ? ? ? print!("{} -> ", i.data);

? ? ? ? ? ? ? ? self.print(&i.next)

 ? ? ? ? ? }

 ? ? ? }

}        

Now let us look a bit deep into this implementation. print() method takes in an immutable reference of itself and an immutable reference to the link enum where we shall be passing in sll.head from main (yes this is not a good way to do it and I have cut a few corners to make it work). Once we have our variables to work with we introduce a rust pattern matcher that handles the branches of our enum object namely Link::Empty and More(i). We return out of function when our link variable presents us with an Empty object and prints the data from the More() branch. Notice that we have used recursion in our ore branch to call the same function with an immutable reference to i.next (which is basically the next object) thereby eliminating the need for maintaining duplicate variables to take care of the actual linked list and this was possible only due to the fact that we provide in only immutable references to our function which has read-only access thereby protecting the function from any unwanted mutation by mistake.?

And that’s it folks we have successfully implemented our very own singly linked list on rust and goodness gracious wasn’t it one hell of a ride. I know this is still not a really good way to implement this data structure on rust but I did love the learning experience doing so on rust. Feel free to comment if you liked my opinions on rust and all the different ways and optimizations I can do for these functions that I have presented here.

Thanks for your time and be seeing you on the next post.