Implementing a Linked List In Javascript … From Scratch
When first learning about data structures, you likely encountered something called a linked list. What exactly is a linked list? Well it may be useful to draw a comparison to a data structure you likely are familiar with, an array. Like an array, linked lists store data in “nodes” which are single elements that make up a linked list. However, each “node” has a next property that points to the next “node” inside the linked list. The first node in a linked list is called the head and the last node in a linked list is called the tail.
What are some benefits that linked list have over arrays? One of the biggest advantages that linked list have are the fast operations that can happen at the ends (the head and tail). If you are familiar with big O notation, adding elements to the beginning and end of a linked list are O(1) operations. This means that these operations will always be done in constant time; it does not matter how big the linked list is. Now if you think about adding an element to the beginning of an array or even the middle, you would have to “scoot over” all the elements that come after that index.
Another big advantage is the flexible size of linked list; you don’t need to specify how many elements you need to store ahead of time. Unless you are utilizing a dynamic array, you usually have to declare how many elements you plan on storing in that array ahead of time.
One of the disadvantages of a linked list is the slow lookup time. Unlike an array, a node cannot be accessed by the “index”. You would have to traverse the entire linked list until you get to the desired element. The lookup operation for linked list is O(n), or linear time, meaning it does depend on how large the linked list is.
I have found that the best way to learn about a new data structure and really gain understanding about it is to implement it yourself. So that is exactly what we are going to do in the next section!
Creating a Node and Linked List Class
So let’s start off by implementing a single node that will eventually link together to form a linked list. A node is going to take in two constructor arguments, one called data that will hold information for that particle node and one called next that points to the next node in the linked list.
Now that we have a node, let’s build out the skeleton for the linked list. In our implementation, we will only have a head property for our linked list that points to the first node in the linked list, but feel free to try and implement a tail property. Our linked list class is initially going to take an argument of what we should set as the head. If you have the head of a linked list, you essentially have the entire linked list. Why? All the nodes are connected with the next property. The head points to the next node in the list, the next node points to the next node in the list, and so on.
Now that we have the basic skeletons down, we can start to write some useful methods for our linked list class.
Find The Size of Our Linked List
One very useful method we might need is to find out how many nodes we have in our linked list. In order to implement this method we can initiate a variable called node and a variable counter . We can then traverse the linked list and increment counter until there is no “next” node or node.next === null.
Get the First and Last Element of the Linked List
Now let’s write two new methods, one to obtain the first node in the linked list and one to obtain the last node. What is the first element in a linked list? Yes, you are correct, that would be the head. Getting the last element is a little trickier. We could implement a very similar approach to the size method. However, instead our while loop condition will change to node.next . This is because we want node to stop at the last node in the linked list. If we set the while loop condition to be node , our final value for node would always be null .
Insert an Element at the First and Last Position
Next, let’s implement a method to insert a node at the first and a method to a node at last position of the linked list. For the insertFirst method, we would take in a data argument to create a new node. We would then set this new node as the new head and set the next property to the previous head of the linked list.
For the insertLast method, we could utilize the getLast method we have previously written. Once we have the last element, we can set the next node to the new node that we are creating.
Insert and Remove an Element in a Specific Position
The next couple of methods are a little trickier than what we have done so far. We want to write a method to insert a node at a specific index and remove a node at a specific index. In order to accomplish this, we can write a getAt method that returns the node at a specific index in our linked list.
Once we have the getAt method, we can use it to implement our other two methods. For the insertAt method, we will obtain the node right before the index that we want to insert at. This way we can set the next property of that previous node to new node. The new node next property will then be set to what used to be the next of the previous node. We also have to take into consideration edge cases, such as if the specified index is out of bounds.
The removeAt method has the same idea as the insertAt method but now we are removing the next node by setting the next property of the previous node to two nodes ahead or prev.next.next . We do have the ability to chain next calls like this. Now nothing is pointing to the prev.next node so it is essentially “removed” from the linked list.
Final Thoughts
Linked list are definitely an interesting data structure and may come up during your coding interviews. I encourage you to come up with some other methods that you can add to our linked list implementation.
One very helpful course I recommend if you want to dive deeper into other data structures and algorithms is:
https://www.udemy.com/course/coding-interview-bootcamp-algorithms-and-data-structure/
