In this post, we will look at a typical Linked List Implementation in Javascript. In particular, we will look at Singly Linked List.
As you might be aware, Linked List is an extremely popular data structure. Basically, it forms the basis for many other complex Data Structures. Therefore, it is important to understand how Linked List Implementation works.
In an earlier post, we implemented Linked List in Java. However, in this post, we will use Javascript and the new ES6 class syntax.
1 – The Node Class
The Node is the most important aspect of a Linked List. In other words, Node is a single element in a Linked List. Basically, a Linked List is a collection of nodes.
In a Singly Linked List, each node points to the next node in the series. However, in a Doubly Linked List, each node points to the next node as well as the previous node in the list.
Below is a simple Node class definition:
class Node { constructor(val){ this.val = val; this.next = null } }
Basically, there are only two properties. The first one is the value or val. The second is the reference to the next node.
2 – The Linked List Class
The next important piece in Linked List implementation in Javascript is the the actual Linked List class.
A typical class definition for the same is as below:
class SinglyLinkedList{ constructor(){ this.length = 0; this.head = null; this.tail = null; } }
Here, we have only 3 properties. First is the length property. Basically, this stores the current length of the Linked List. Next, we have the head property that points to the first element in the list. In other words, the head element. Lastly, we have the tail property pointing to the last element in the list.
3 – Linked List Implementation Operations
To work with a Linked List, we also have to define several operations. These operations can range from pushing a new element or popping an element from the linked list. Also, you can have operations to insert or remove elements from the list. Basically, all these operations are part of the SinglyLinkedList class itself.
Let’s look at these operations one by one:
3.1 – The Push Operation
The job of the Push operation is to add a new element at the end of the Linked List.
Below is the implementation:
push(val){
let newNode = new Node(val)
if (this.length === 0){
this.head = newNode;
this.tail = newNode;
this.length++;
}else{
this.tail.next = newNode;
this.tail = newNode;
this.length++
}
return this;
}
Since we already keep track of the tail of the Linked List, this operation has a time complexity of O(1). In other words, it finishes in constant time.
Basically, we just create a new Node using the Node class. Next, we add the Node to the next element of the tail and update the tail.
3.2 – The Pop Operation
The Pop operation removes the last element from the Linked List. In other words, it removes the tail of the Linked List and makes the previous element of the tail as the new tail.
Below is the implementation for the same:
pop(){
if(this.length === 0) return undefined;
let currentNode = this.head;
let prevNode = currentNode;
while(currentNode.next){
prevNode = currentNode;
currentNode=currentNode.next;
}
prevNode.next = null;
this.tail = prevNode;
this.length--;
return currentNode;
}
If you notice the above code, the Pop operation has a time complexity of O(n). This is because to pop the last element, we have to traverse through the whole list one node at a time.
Even though we have a direct reference to the tail element but we don’t have any reference to the previous element to the tail. To pop the last element or the tail, we need to make the tail’s previous element as the new tail. And to do so, we have to traverse the list from the beginning so that we can keep track of the previous node.
3.3 – The Shift Operation
Shift operation removes the first element or the head of the Linked List.
Below is the implementation:
shift(){
if (this.length === 0) return undefined;
let currentHead = this.head;
this.head = this.head.next;
this.length--;
return currentHead;
}
As can be seen, this operations has time complexity of O(1). This is because, we have a direct reference to the current head of the Linked List. Using the same, we can assign a new head element and remove the current head.
3.4 – The Unshift Operation
The Unshift operation adds an element at the beginning of the Linked List. In other words, it creates a new head for the existing Linked List.
Below is the implementation for the same.
unshift(val){
let newNode = new Node(val)
if(this.length === 0){
this.head = newNode;
this.tail = newNode;
}else{
newNode.next = this.head
this.head = newNode;
}
this.length++;
return this;
}
This operation also has a time complexity of O(1). Since we already have a reference to the head, we can easily establish a new head. The only edge case over here is when we have an empty Linked List. To handle that scenario, we first check if the length of the list is 0. If it is true, then we assign the new node as both the head and the tail.
3.5 – The Get Operation
The Get operation is used to find the Node at a particular index in the Linked List.
Below is the implementation:
get(index){
if (this.length === 0) return undefined;
if (index >= this.length) return undefined;
let counter = 0;
let currentNode = this.head;
while(counter < index){
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
This operation has a time complexity of O(n). Basically, we traverse through the Linked List till we find the index. Then, we return the Node.
We handle some of the edge cases such as an empty list or the index being out of bounds in the beginning of the function itself.
3.6 – The Set Operation
The Set operation is like an update operation. It takes two inputs i.e. the index and the new value that should be assigned to the node at that index.
Below is the implementation for the same:
set(index, val){
let node = this.get(index);
if(node){
node.val = val;
return node;
}
return undefined;
}
This operation also has a time complexity of O(n). However, to make life easy for us, we can use the get(index) function to first find the node. Then, we update the value at that node with the new value.
3.7 – The Insert Operation
The Insert operation inserts a new Node at a particular position in the Linked List.
Below is the implementation for the same:
insert(index, val){
if(index < 0 || index > this.length) return false;
if(index === 0) return !!this.unshift(val);
if(index === this.length) return !!this.push(val)
let newNode = new Node(val);
let prevNode = this.get(index - 1);
let temp = prevNode.next;
prevNode.next = newNode
newNode.next = temp;
this.length++
return true;
}
Here also, we can the use the get(index) function to find the node. And then, insert a new node.
We handle the edge cases in the beginning. For an empty list, we call unshift() function. However, for insertion happening at the end of the list, we use the push() function.
If none of the cases are correct, we traverse to one position previous to the index so that we can insert the new node. This operation also has time complexity of O(n).
3.8 – The Remove operation
As the name suggests, this operation removes a particular node (based on the input index) from the linked list.
Below is the implementation for the same:
remove(index){
if (index < 0 || index > this.length) return undefined;
if(index === 0) return this.shift();
if (index === this.length) return this.pop();
let foundNode = this.get(index - 1);
let toBeRemovedNode = foundNode.next;
foundNode.next = toBeRemovedNode.next;
toBeRemovedNode.next = null;
this.length --
return toBeRemovedNode;
}
Here also, we use some of the existing functions. For example, in case we have to remove the first element, we call the shift() operation. On the other hand, if we have to remove the last element, we call the pop() operation.
Then, we find the node using the get(index) function and remove it. Finally, we update the length property.
Conclusion
With this, we have completed Linked List Implementation in Javascript successfully.
You can find the complete code for the above in the Github gist.
0 Comments