Learning Data Structures: Singly Linked Lists
As I’m learning about data structures and algorithms, I figured it would be helpful for myself and (hopefully) others if I wrote about them to better strengthen my understanding on the topic. Data structures are a collection of values, the relationships among them, and the functions or operations that can be applied to data. When starting out, the more common data structures include arrays and objects. However, there are others that we can utilize that can be more efficient depending on what outcome we are trying to achieve.
For this blog, I wanted to touch on singly linked lists and share some code as to how to create a class and push and pop instance methods for it. First off, a linked list is a data structure that contains a head, tail and length property. Unlike arrays, there is no index. Instead, linked lists consists of nodes and each node has a value and a pointer that connects to another node.
Below, is a very simple snippet of how to create a node class and a singly linked list class. For the node, we need to start with a constructor that takes in a value and assign it as the default property of ‘val’. We do this by having this.val equal to val. We can also create a ‘next’ property and give it a default value of null, as there is no other node when we instantiate our instance.
We can then create a singly linked list class by creating default values for the head and tail. This will start out as null with the list length equal to 0. We’ve just created our very own node and singly linked list class! At the bottom of the code snippet, I’ve also added how we can create a new instance of a node and linked list and assign them to variables, ‘newNode’ and ‘list’ respectively.
Once we have our classes set up, we can start adding other custom instance methods such as push, pop, shift, unshift, get, set, insert, remove and reverse!
Below, I share some code for push and pop along with some comments on my approach to implementing this. For the push method, we simply create a new node and set it to a variable. We have an edge case where if there is currently no head, then we assign the head to be the new node, as well as the tail. Otherwise, we will assign the node after the tail to be the new node. From there, we can assign the tail to be the newly created node. Afterwards, we need to remember to increment our length of the list, as we added a new value and then finally, we can return the list at the end.
For our pop method, we set the head to a variable called ‘current’. We then create another variable and set that to current. Then, we create a while loop where we move through each node until we reach the end of the list.
Once the variable, ‘newTail’ is second to last of the list, we assign that to the tail and assign the next node to be null in order to end the list. This is when we officially pop off the node. Lastly, we need to decrement the length and then return our variable ‘current’, which should be the last node that was popped off from the list! In the code, we also have some conditionals where if we pop off the last node and the length is 0, then we also have to set the head and tail back to null.
As mentioned earlier, there are many other methods we can create within this class, but to keep this post short, I wanted to touch on the push and pop methods for now.
Stay tuned for future breakdowns and learnings through my journey with data structures!
