LinkedList in JavaScript — Implementing the powerful data structure on the web.
Introduction:
Recently, I was preparing for interviews, during which, I decided to explore the intimidating realm of data structure, and javascript being a language that I use in my day-to-day coding, I decided to look for implementations in this language.
Learning data structure is always challenging to most of the frontend developers, but we cannot invalidate its usefulness in a software application.
So what is a Linked List, it is definitely a fundamental & important linear data structure utilised in computer science! you can think of it as a series of nodes linked together using a link, consecutively. So every node in this series has a value, and a reference to its next node. First node of this series is known as the headnode. But but guys, as someone wise has described, A picture is worth a thousand (or a million maybe!) words, so why not see a beautiful picture of our new friend in coding, the linked list?
So as you can see, head has the value 55 , and its pointing next node serially, until it reaches 11 and then the LinkedList ends after the final reference being null, simple, isn’t it? :)
It was a simplified definition of a linked list, what about some operations using this data structure? Let’s dive in! ;P
Adding a node:
Let’s say we want to add a value to our LinkedList, how do we do that? We first declare (instantiate) a node using a Node class (which has a value provided by us & a next reference, initially set to null ) and then according we can place at the end of the list, or at the front of the list. Let’s see both the approaches one by one!
First, let’s see how can we append at the front, it’s quite simple. If the head node doesn’t exist yet, we simply assign our newly instantiated node to the head, otherwise if 1 or more element is present in the list, we first assign the current head as the next node to our newly created node, and then simply declare the new node as the head node. Let’s see the visualisation:
But in case there are already existing nodes, we make the next of our new node pointing to the previous headnode, and then re-assign the head node as the new node!
Oh, let’s see our code implementation also, (sorry, I just completely forgot that, hehe)
First we will declare a Nodeclass, and also a LinkedListclass, and inside the linked list class, we will have a method called appendAtFront , this method will take the value as an argument, and then create the node using the Node class. and then we will check the existence of head node, if it is not there, we will declare new node as the head as previously stated, otherwise we will adjust the existing nodes to make the room for our new node (see the pic. for reference). Also, we are maintaining a size variable, which we increase after adding a subsequent node.
Okay, let’s consider our next scenario, which is appending at the end of the list.
So, as per our previous scenario, if there is no head we will simply assign the new node as head node.
Otherwise, we will run a loop that will iterate by moving to the next node. And we will maintain the current node reference, and once we found null reference in next reference of the current node, we conclude it as the end of the linked list. And then we add the next reference of that node to our newly created node. Let’s see the code!
Now, the last scenario we will be looking at is appending at any index provided. It is a simple procedure, we will maintain a count variable by instantiating as 0, and will be looping through the list, per each iteration, we will be incrementing the count . we will maintain a prev variable to track the previous node & a curr variable to track the current node, And once we found our desired index , we will point the prev node’s next node to our newly instantiated node & assign the curr node as the next node to the new node. Easy peasy!
Let’s see the visualization & the code:
Also, if the index is 0 or size , then we simply call our previously defined this.appendAtFront or this.appendAtRear methods.
That’s it guys, now we have the superpower to add a new node wherever we want in a Linked List, let’s move forward to our next section, which traversing the list!
Traversing a Linked List:
Now that we have added nodes into our linked list, we need a way to see all the nodes present in the list. We can draw inspirations from the previous methods to achieve this. We need to iterate through all the values in the list, and as we move forward, we will append the nodes values to a string. And later, we will simply return it. I guess we don’t need the picture for the traversal, as we have already explored the idea of traversing through the nodes previously, so let’s directly jump into the code!
Now let’s move forward the last part of this article, which is about deleting a node using its value.
Deleting a node using its value:
While deleting using its value, we will simply iterate through by moving using the next pointer, we will maintain a prev node to track the previous node & curr node throughout the loop, and once we found that the value of our current node equates the the value that has to be deleted, we reference the next pointer of prev node to the curr.next node & make the next of curr node as null .
Lets look at the picture for crystal clear understanding:
Let’s see the code below (we have handled some edge cases like when the list is empty or when the head node itself has to be deleted):
Conclusion:
That’s it guys, I hope I am able to clear many of your doubts regarding the linked list data structure, do let me know your feedback, thanks & see ya later!!! :)
