How to create a linked list in JavaScript
Linked Lists are data structures that are similar to arrays but do not possess indexes, rather, the head node points to the next node in memory.
Linked list as the name implies are lists of nodes that are linked together. They are similar to arrays and hash tables but are more dynamic which means that values can be inserted in the middle of a list without collision or order.
What is a node?
The aim of this article is to simplify breakdown concepts into tiny bits for easy assimilation. A node simply is a bucket of information stored in memory that possess a value and points to the next node.
In a linked list, the first node is called the head while the last is the tail, they possess a pointer which points to the next node in memory. A pointer is a reference to another place (node) in memory.
Building our linked list:
JavaScript doesn't have a prebuilt linked list function unlike Java, and we would learn how to build a linked list that appends and prepends lists in memory.
Prepend O(1) : This means to add a node to the beginning of a linked list. It has a Big O notation value of O(1) because no looping is involved.
Append O(1): This means to add a node to the tail of a linked list and has the same Big O notation of the prepend method.
Lets dive in:
I hope we are familiar with object oriented programming in JavaScript where we use a constructor function to instantiate an object. If we are, then we would also be familiar with the this keyword. The this keyword simply is a reference to the instantiated object within the objects’ class.
Step 1: Instantiate an object with whatever class name, we would use LinkedList in our demonstration.
As seen in the code above, this class has a constructor function called value which could be accessed throughout the object class LinkedList.
We instantiate the first node in our linked list which is the head and this head possess values namely the input which is the value and the next node which would be set to null, we set it as null because we could only have a node in memory and we wouldn’t want an error if we have otherwise.
The tail which is the last node in a linked list would inherit the values of the head since it’s also a node, and all nodes should possess a given value. We also give the linked list a length of 1 and this increments as we add items to our linked list.
Step 2: Write a function that appends item(s) to the linked list
Here, we write a method in our LinkedList class that takes in a value as input. We create a newNode that has a value and next as null similar to when we wrote our constructor function in step 1. We then assign the next node this.tail.next the properties of newNode so that it has a value. We also give it a tail since every linked list should have a tail i.e. 2 linked list items should have 1 tail, 4 linked list items should also possess 1tail as well. We then increment the length so that the new length of our linked list increases and we finally return this which is our function.
As seen in the above result from the console.logs(), we can observe that the head has a value of 10 and a next value (node) of 5 with 5 having a next value of 16 making it the tail of our linked list. We have successfully appended 5 and 16 to our linked list.
Step 3: Write a function that prepends item(s) to the linked list
This is similar to our first append function, here we only have to put item(s) at the beginning of our linked list. Let’s dive in …
Here, we write a prepend function that also requires a node with value. First, we make the head node in our linked list become the next node with the new head node taking the properties of the newNode object. We then increment the length so we could see in our console.log that a new node has been created and finally, we return the function.
Here, we see that the head of our linked list takes 2 as its value, while the previous head with value 10 becomes the next node of the new head. The node with value 5 still points to node value 16 as its next value which is ultimately the tail of our 4 value linked list.
Thanks for reading…. and a big shoutout to Andrei and the ZTM community.
