Linked List Data Structure In JavaScript
Understanding one of the fundamental data structure in computer science
Linked List Data Structure
In this tutorial, you will learn about linked list data structure and it's implementation in JavaScript.
A linked list is a linear data structure that includes a series of connected nodes. Here, each node stores the data and the address of the next node.
Linked lists can be of multiple types: singly, doubly, and circular linked list. In this article, we will focus on the singly linked list.
what is Singly Linked List ?
Singly Linked List is an ordered set of data elements, each data element containing link to its next element.
Linked list will have nodes , each node represent a data element. a node is represented by an object in javaScript. each node has two parts
Data part where the actual value of the node will be stored.
The reference part which will store the reference to the next element.
All nodes are connected to each other with the help of the references.
The starting node will be called as head node and the ending node of linked list is called the tail node. we store the references of the head node and tail node to make the operations of linked list easy to perform.
Understanding the Singly Linked Lists
In this section of the tutorial we will learn about the structure of linked list and how various operations are performed on linked lists intutionally and then we will dive deep into code for each operation.
We will create two classes Node, SinglyLinkedList
Node class will store the actual data and reference to the next element .
SinglyLinkedList class will store the head reference and tail reference of the List and the length of the list and methods to implement the functionalities of Linked Lists.
Code :
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList{
constructor(){
this.head = null;
this.tail = null;
this.length = 0;
}
}
Now lets implement a small printLL function to print the all elements in the linked list.
printLL():
step-1 : Check if the head is null , if yes it means list is empty so return undefined or some message.
step-2 : Create a temp variable to store the node and it will get updated in iterations.
step-3 : Loop through the list until the temp !== null and console.log the temp node's value and update the temp with its next element.
Code :
print() {
if (this.head === null) console.log("list is empty");
let tempNodeStore = this.head;
while (tempNodeStore !== null) {
console.log(tempNodeStore.val);
tempNodeStore = tempNodeStore.next;
}
}
2. Now we will see how to implement the functionalities
* push()
* pop()
* shift()
* unShift()
* get()
* set()
* insertAt()
* remove()
3. ### push(val) :
* Now we will see exact steps to take in order to push the node to the end of the list.
* #### step-1 : Make a new node with given value
* #### step-2 : Check if list is empty by checking if head is empty , if head is empty then make the new node as both head and tail of the list.
* #### step-3 : If list is not empty then there is elements in the list , so now we need to add the new node to end.
* Point the current tail's next prop to the new node
* Change the current tail to the new node
* #### step-4: Increment the length prop of the list.
* #### Code :
push(val) { let newNode = new Node(val); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; this.tail = newNode; } this.length++; return this; }
4. ### unShift(val) :
* Add the node in the beginning or start of the list
* #### step-1 : Make a new node with passing val.
* #### step-2 : If list is empty then make the new node the head and tail.
* #### step-3 : Otherwise
* Make the newNode's next prop point/referencing to the current head
* Change the current head to the new node.
* #### step-4 : Increment the length of the list.
* #### Code :
unshift(val) { let newNode = new Node(val); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { newNode.next = this.head; this.head = newNode; } this.length++; return; }
5. ### shift() :
* Remove the element from the beginning of the list.
* #### step-1 : If list is empty return null or a message that list is empty
* #### step-2 :
* Store the current head in the variable.
let current = this.head
* Set the current head's next as the current head.
this.head = current.head
* Decrement the length by 1.
* If the length of list is zero then make the tail point to null.
* #### Code :
shift() { // removes the first beginning element of the array if (this.head === null) return; let curHead = this.head; this.head = currHead.next; this.length--; if (this.length === 0) { this.tail = 0; } return curHead; }
1. ### pop() :
* Remove the last element of the list.
* #### step-1 : Check if the head and tail is null if yes , return null or list empty message.
* #### step-2 : Loop through the list and store the current element and its prev element , when loop ended we will have the last element and its previous element .
* #### step-3 : Set the tail to the prevElem and tail's next to null and decrement the length by 1. by doing this we completely removed reference to the last element.
* #### step-4 : Check if the length is 0 , if yes make head and tail to null.
* #### Code :
```plaintext
pop() {
if (this.head === null || this.tail === null) console.log("list is empty");
let current = this.head;
let prevCurrent = current;
while (current.next) {
prevCurrent = current;
current = current.next;
}
this.tail = prevCurrent;
this.tail.next = null;
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return this.tail;
}
get(index) :
Get the node by the index number , index starts with zero.
We need to simulate the indexing on the list rather than array with builtin indexing.
step-1 : Check if given index < 0 or index >= length of list if anyone of the condition is true then return error message or null.
step-2 : Initialize the counter variable starting from 0 and will gets incremented in the loop. we will loop through the list until the counter < index and update the temporary variable with current node.
step-3 : After the loop ended the temporary node will contain the node at the index and we will return the temporary node.
Code :
get(index) {
if (index < 0 || index >= this.length) return null;
let counter = 0;
let tempNodeStore = this.head;
while (counter < index) {
tempNodeStore = tempNodeStore.next;
counter++;
}
return tempNodeStore;
}
set(index, val) :
We will edit the node by getting it by index
step-1 : Get the element by index
step-2 : Edit the node with new value.
Code :
set(index,val){
let currNode = this.get(index)
currNode.val = val;
return this;
}
insertAt(index, val)
We will insert the new node at the given index .
First we need to find the element at (index - 1) and then use it to place the new node after it and connect the new node to its next element.
step-1 : Check if the passed index < length and index >= length , if yes then return error msg or undefined.
step-2 : Create a new node with that value
step-3 : Use the get method that we previously built and get the element with index of (index - 1) and store it some variable called temp.
step-4 : Now set the new node's next prop to temp's next, in that way the new node is connected to its next element that should be there after insertion.
newNode.next = tempPrevNode.next
step-5 : Now set the temp's next to point to the new node , in that way we created a connection between the previous element and the element at given index. now we have adjusted the references so that the new node will be present in the given index.
tempPrevNode.next = newNodestep-6 : Increment the length and return the linked list.
Code :
insertAt(index, value) {
if (index < 0 || index >= this.length) return null;
let newNode = new Node(value);
let tempNodeStore = this.get(index - 1)
newNode.next = tempNodeStore.next;
tempNodeStore.next = newNode;
this.length++;
return this;
}
removeAt(index)
Removing the element at the given index , in order to do that we need get both the element at the given index and prev element of that given index.
step-1 : Check if the passed index < length and index >= length , if yes then return error message or undefined.
step-2 : Here we can use previously built get method for getting the element at index and index - 1. but now we will see an other approach which just uses the loop to get the element at index and index - 1 on the same loop.
step-3 : Now we will maintain two variables that stores the current element and prev element of current element in the iterations. now we will loop through the list with condition counter < index that means when the counter become equal to the index it stops , when it stops we will have element at index and element at index - 1 at the end of loop.
while (counter < index) {
prevNode = currentNode;
currentNode = currentNode.next;
counter++;
}
step-4 : Set the prevNode's next to the currentNode's next value , so by doing this we completely erased the link the element at given index.
prevNode.next = currentNode.next;
* #### step-5 : Decrement the length and return the list or a boolean to represent the end result. * #### Code :
remove(index) {
if (index < 0 || index >= this.length) return null;
let currentNode = this.head;
let prevNode = currentNode;
let counter = 0;
while (counter < index) {
prevNode = currentNode;
currentNode = currentNode.next;
counter++;
}
prevNode.next = currentNode.next;
this.length--;
return true;
}
Complexity Analysis
Both Time Complexity and Space Complexity of push(), unshift(), shift() is O(1) constant time and space.
The time complexity of pop() is O(n) linear time and space complexity is O(1).
The time complexities of both get() and set() is O(n) linear and space complexities are O(1) constant.
The Time Complexity of insertAt() is O(n) because it uses the get() function which is of O(n) , so it also becomes O(n) linear. the space complexity is O(1) constant .
The Time Complexity of removeAt() is also O(n) linear because it uses the get function in it which would still take O(n) time. the space complexity is O(1).
Major Disadvantages of using the Linked Lists
One of the major disadvantage of singly linked list is there is no reverse connection to the prev elements of the node , we can see that in singly linked list when we are building the reverse traversing or reverse indexing like get the last element with index -1 or getting last 2nd element with -2 index , surely we can build that but it becomes very complex with singly linked list.
To solve that disadvantage of reverse traversing , there is an extension to singly linked list called doubly linked list , my next tutorial will be on doubly linked list.
Wrapping Up
Oof, we are done! I know that there are many functionalities that we have built in linked list but these are purposefully put in here because if a learner need to understand and get a good grasp of the concept he/she should play and practise on it more time . It took me time to put everything together, and you don’t have to understand everything at once. One reading will give you a good overview of all the functionalities and the concept of linked list, but you may need to read the article more than once and focus on building each functionality on your own by understanding the steps of each method to grasp all the concepts.
Before I end, I want to say something that this is my first article in my life that i am writing if u have any feedback or changes or additions that are needed in this article please let me know i will add them. you can reach me out on twitter and email.
My email is gowthamujjineni@gmail.com , feel free to reach me out .