LinkedList Implementation In Javascript

Introduction

The linked list is one of the most popular linear data structures!

But wait, linear, how?

• By definition, a linear data structure arranges its elements in a linear fashion, where one element is connected to the next and previous element. When we started learning the program, we all came across arrays; Arrays are the best example of linear data structure; they store elements index-wise in a linear trend. But arrays have some limitations, one of them being a fixed size. This can be solved with LinkedList.

So basically, LinkedList is a list of nodes, but now what on earth is a node?

• Well, the node is a user-defined class that holds 2 properties. The first property is the value to be stored, and the second is the pointer to the next node; as you can see in Image 1 below, we have a node with a value of 10, and it's pointing to node 2.

Image 1- Single Node in a LinkedList

What are we going to learn in this article?

1. How to create a node
2. How to create a LinkedList class with a head node
3. Print LinkedList
4. Add tail node
5. Add a new head node
6. Inserting a node in between a LinkedList
7. How to delete a head node
8. Delete a tail node
9. Delete a node by index
10. Delete a node by value
11. Search an element in the LinkedList

1. Create a Node

Listing 1 shows how to create a Node class in JavaScript. Create a class Node, which will take value in a constructor and create 2 properties: value and next; next is the pointer which will get assigned as we code ahead. For now, let's say it's null, we will learn the reason why it has been set to null in the beginning. 

class Node {
    constructor(value){              
        this.value = value,
        this.next = null       
    }
}

Listing 1- Node class in JavaScript

But why do we need pointers, though? Since a Node is an object, a list of nodes would be scattered across the memory, so the elements are not stored at contiguous memory locations. We need to connect them with some mechanism; that mechanism is pointers. Pointing to the memory location of the next node where the object is being stored.

We need a pointer to arrange elements in a linear fashion. Image 2 shows the visual representation of a LinkedList with 2 nodes.

Image 2- Pointers

Tail

In the above image, you can see there are 2 nodes, Node 1 has data which is 10, and then a pointer pointing to node 2. But Node 2 isn't pointing towards anything; in fact, it's pointing towards null; the same question we had before, what is the deal with this null?

Now we know pointers are used to point to the next node, but there has to be an end of the list. So when a list has the last element pointing towards nothing, it points towards null, specifying this is the last node, also known as a tail node. So in Image 2, Node 2 is a tail node.

Head

In the same way, we need to start somewhere, right? When we create the first element in a LinkedList, it's always ahead. i.e., we always start from the head. So the above image can also be seen as the below one.

Image 3- Head and Tail

2. Create a LinkedList class

As we said earlier, a LinkedList is a collection of nodes, so we need to create a class that adds, deletes, and searches these nodes. We always start with at least one node to create a LinkedList. So we can create this first node which would be the head of the list, with the help of the constructor. 

class LinkedList{ 
    //Creates a linkedlist with passed value.
    constructor(value){ 
        //Creates a head node      
        this.head = {
            value: value,
            next : null
        };
        //As there is only one element in the list, head is also a tail
        this.tail = this.head;
        //Length would be 1
        this.length = 1;
    }
}

Listing 2- LinkedList class with a constructor

In listing 2, you can see we are creating a single node in a constructor with a parameter's value, and since currently there is only one element in this LinkedList, this node is both head and tail, and the current length of this list would be 1. 

Let's create an instance of LinkedList. 

console.log('Creating a LinkList at constant time O(1): 20:');
const myLinkedList = new LinkedList(20);
console.log(myLinkedList);

Listing 3- Creates a LinkedList with a value of 20.

Run the code and check the console of the browser. You will be able to see the output as shown in image 4.

Image 4- Output of listing 1 and 2

3. Print a LinkedList

For that, we need to write a printList() method. The more elements you add to the list, the more complex the output will look. So to simplify, let's print just the values.

printList(){
    //Creates an empty array.
    let printArrayList = [];

    //Pointer which points to the head node
    let currentNode = this.head;

    //Start iterating from the first node till you reach the last node
    while(currentNode !== null){
        //Add every node's value to the array
        printArrayList.push(currentNode.value);

        //Point pointer to the next node
        currentNode = currentNode.next;
    }
    //Return the array
    return printArrayList.join(' -> ');
}

Listing 5- Print the LinkedList

In the above listing, you can go through the comments; they are pretty self-explanatory. Now run the code again. This time, you'd be able to see the output as below.

Image 5- Printing LinkedList

Image 6- LinkedList with node 20

4. Add a new tail node 

We learned how to add a head node; now, let's see how to append a node; every appended node becomes the new tail of the list.

//Add the node at the tail of the linkedlist
append(value){

    //Create a new Node by creating a instance of a Node class
    const newNode = new Node(value);

    // Check if head is present or not, if head is empty creates a head
    if (this.head == null){
        this.head = node;
    } 
    else{ //Else creates a tail

    //We need to point current tail's next to the newNode
    this.tail.next = newNode;

    //Now make newNode a tail node
    this.tail = newNode;

    //Increase the length by 1
    this.length++;        
    }
    return this;
}

Listing 6- append method of LinkedList class

By calling the append method twice, let's append 2 nodes with 40 and 50.

 console.log('Appendding Node at constant time O(1): 40 -> 50:');
 myLinkedList.append(40).append(50);
 console.log(myLinkedList.printList());

Listing 7- Adding elements in an array

Image 7- Output of Listing 6 and 7

Image 8- Appended 40 and 50

5. Adding a new head node

To add the new node as head, we must move the current head to the one position ahead.

//Add the node as a head of the linkedlist
prepend(value){
    //Create a new Node by creating a instance of a Node class
    const newNode = new Node(value);

    //Points this node's next to the head
    newNode.next = this.head;

    //Now make this node a head node
    this.head = newNode;

    //Increase the length by 1
    this.length++;

    return this;
}

Listing 8- Adding a head

Now, call this method and prepend a node with the value 10.

console.log('Prepending Node at constant time O(1): 10:');
myLinkedList.prepend(10);
console.log(myLinkedList.printList());

Listing 9- Calling a prepend method

After adding a new node 10, your output would look like this,

Image 9- Output of listing 7 and 8

Image 10- Prepended 10

6. Inserting a node by index

Let's insert a new node at the given index. To insert an element in the middle, we have to traverse to the previous node, then divide the list into 2 parts; first, merge the right side of the list with the new node and then assign the left. Go through the comments to understand each step.

//Insertes a node at specified index, say we want to insert 30 at index 2
//Current list: 10 -> 20 -> 40 -> 50
insert(index, value){
    //Create a new Node by creating a instance of a Node class
    const newNode = new Node(value);

    //Counter to loop
    let count = 1;

    //Create a temp node to traverse through list, which will start from the head node
    //Pointing to 10
    let previousNode = this.head;

    //Traverse the list one node before the specified index, which is previous node
    while(count < index){
        //Point previous node to next for iterating
        previousNode = previousNode.next;

        //Increase the count to compare it with index;
        count++;
    }
    //When the loop ends you will be able to have a previous node. Which is 20 in this example.

    //First, points new node's next to the previous node's next, so it can hold the list ahead of its index
    //New node = 30, So new node will be 30 -> 40 -> 50
    newNode.next = previousNode.next;
    
    //Now just point previous node's next to new node.
    //Merge left side of the list, 10 -> 20 -> 30 -> 40 -> 50
    previousNode.next = newNode;
    return this;
}

Listing 10- Inserting a node in a LinkedList

Let's call this method.

console.log('Inserting Node at index 2 with time complexty of O(n): 30');
myLinkedList.insert(2,30);
console.log(myLinkedList.printList());
console.log('Inserting at index 1: 15');
myLinkedList.insert(1,15);
console.log(myLinkedList.printList());
console.log('');

Listing 11- Inserting 30 and 15 in the LinkedList

Image 11- Output of listing 9 and 10

Image 12- Inserted 15 and 30

Delete operations

There are 4 possibilities for deleting a node from the linked list.

1. Delete head
2. Delete tail
3. Delete at index
4. Delete the node with the value

7. Delete head

Deleting the head is easy; make the next element a new one. Then reduce the length by 1.

deleteHead(){
     this.head = this.head.next;
     this.length--;
     return this;
}

Listing 11- Delete head

console.log('Deleting Head-Node at constant time O(1): 10:');
myLinkedList.deleteHead();
console.log(myLinkedList.printList());
console.log('');

Listing 12- Calling a deleteHead method

Image 13- Output of listing 11 and 12

Image 14:-eted head node 10

8. Delete Tail

Traverse till the second last node in the list and point its next to null.

deleteTail(){
     let secondLastNode = this.head;
     while(secondLastNode.next.next !== null){
         secondLastNode = secondLastNode.next;
     }
     secondLastNode.next = null;
     this.length--;
     return this;
}

Listing 13- Delete tail

console.log('Deleting Tail-Node at O(n) time: 70:');
myLinkedList.deleteTail();
console.log(myLinkedList.printList());
console.log('');

Listing 14- Calling a deleteTail

Image 15- Output of listing 13 and 14

Image 16- Deleted tail node 50

9. Delete a node by index

Now you know how to traverse to the previous node; once you reach the previous node, point it next to the next, next, which will skip the middle node. 

Note: First, you must check whether the deleting node is the head.

deleteAtIndex(index){
   //Check if index is head
   if(index === 0){
    //Appoint head to the next element
    this.head = this.head.next;
    this.length--;
    return this;
   }
let count = 1;
let previousNode = this.head;
while(count < index){
    previousNode = previousNode.next;
    count++;
}
previousNode.next = previousNode.next.next;
this.length--;
return this;
}

Listing 15- Delete node at the specified index

console.log('Deleting Node at index 2 with time complexty of O(n): 30:');
myLinkedList.deleteAtIndex(2);
console.log(myLinkedList.printList());
console.log('');

Listing 16- Calling deleteAtIndex method

Image 17- Output of Listing 15 and 16

Image 18- Deleted Node at index 2

10. Delete a node by value

Deleting a node by value. We will need 2 pointers for this, first to traverse the list and second to point to the previous node to update the previous node's next pointer. Following listing 17 is a step-by-step process of how we are supposed to achieve this. Follow the comments for a clear understanding. 

deleteNodeByValue(value){
    //Current node to loop through the list
    let currentNode = this.head;

    //Previous node to update its pointer to next.next node
    let previousNode = null;

    while(currentNode != null){
    
        //Check if we find the value we are looking for
        if(currentNode.value === value){

            //Check if it is a head or not by comparing previous node with null
            if (previousNode === null) {
                //If it is head, then update head to nextnode
                this.head = currentNode.next;
            }
            else{
                //If it is not head then simply update previous node 
                previousNode.next = currentNode.next;
            }
            //Reduce length by 1
            this.length--;
        }

        //Previous node will point to this node with every iteration
        previousNode = currentNode;
        //Current node will point to next node for iteration
        currentNode = currentNode.next;
    }
    return this;               
}

Listing 17- Deleting a node with the specified value

console.log('Deleting Node with value 40 with time complexty of O(n):');
myLinkedList.deleteNode(40);
console.log(myLinkedList.printList());
console.log('');

Listing 18- Calling DeleteNodeByValue

Image 19- Output of listing 17 and 18

Image 20- Deleted Node with value 40

11. Search an element

It's the simplest: traverse the list, compare the value, and return true or false.

searchElement(value){
    let currentNode = this.head;
    while(currentNode !== null){           
        if(currentNode.value === value) return true;       
        currentNode = currentNode.next;
    }
    return false;
}

Listing 19:-Searching for an element

console.log('Searching for value 20 with time complexty of O(n):');
console.log(myLinkedList.printList());
console.log(myLinkedList.searchElement(20));
console.log('Searching for value 50 with time complexty of O(n):');
console.log(myLinkedList.searchElement(50));

Listing 20- Searching for 20 and 50

Image 21- Output of listing 19 and 20

Image 22- Found element 15, returned false for node 50

LinkedList.js

And finally, here is the whole code. Let's call it LinkedList.js

class Node {
    constructor(value){              
        this.value = value,
        this.next = null       
    }
}

class LinkedList{
    
    //Creates a linkedlist with passed value.
    constructor(value){ 
        //Creates a head node      
        this.head = {
            value: value,
            next : null
        };
        //As there is only one element in the list, head is also a tail
        this.tail = this.head;
        //Length would be 1
        this.length = 1;
    }  

    //Add the node at the tail of the linkedlist
    append(value){
        //Create a new Node by creating a instance of a Node class
        const newNode = new Node(value);
        // Check if head is present or not, if head is empty creates a head
        if (this.head == null){
            this.head = node;
        } //Else creates a tail
        else{
        //We need to point current tail's next to the newNode
        this.tail.next = newNode;
        //Now make newNode a tail node
        this.tail = newNode;
        //Increase the length by 1
        this.length++;        
        }
        return this;
    }
    
    //Add the node as a head of the linkedlist
    prepend(value){
        //Create a new Node by creating a instance of a Node class
        const newNode = new Node(value);
        //Points this node's next to the head
        newNode.next = this.head;
        //Now make this node a head node
        this.head = newNode;
        //Increase the length by 1
        this.length++;
        return this;
    }

    //Insertes a node at specified index, say we want to insert 30 at index 2
    //Current list: 10 -> 20 -> 40 -> 50
    insert(index, value){
        //Create a new Node by creating a instance of a Node class
        const newNode = new Node(value);

        //Counter to loop
        let count = 1;

        //Create a temp node to traverse through list, point it to the head
        //Pointing to 10
        let previousNode = this.head;

        //Traverse the list one node before the specified index
        while(count < index){
            //Points temp node to its next node
            previousNode = previousNode.next;

            //Increase the count to compare it with index;
            count++;
        }
        //When the loop ends you will able have temp node pointing to the previous node of the index.

        //First, points new node's next to the current node's next, so it can hold the list ahead of its index
        //Current node = 20, New node = 30, So new node will be 30 -> 40 -> 50
        newNode.next = previousNode.next;
        
        //Now just point current node's next to new node.
        //Merge left side of the list, 10 -> 20 -> 30 -> 40 -> 50
        previousNode.next = newNode;
    }

    deleteHead(){
         this.head = this.head.next;
         this.length--;
    }

    deleteTail(){
        let secondLastNode = this.head;
        while(secondLastNode.next.next !== null){
            secondLastNode = secondLastNode.next;
        }
        secondLastNode.next = null;
        this.length--;
   }
  
   deleteAtIndex(index){
       if(index === 0){
        this.head = this.head.next;
        this.length--;
        return this;
       }
    let count = 1;
    let previousNode = this.head;
    while(count < index){
        previousNode = previousNode.next;
        count++;
    }
    previousNode.next = previousNode.next.next;
    this.length--;
    return this;
    }

    deleteNodeByValue(value){
        //Current node to loop through the list
        let currentNode = this.head;

        //Previous node to update its pointer to next.next node
        let previousNode = null;

        while(currentNode != null){
        
            //Check if we find the value we are looking for
            if(currentNode.value === value){

                //Check if it is a head or not by comparing previous node with null
                if (previousNode === null) {
                    //If it is head, then update head to nextnode
                    this.head = currentNode.next;
                }
                else{
                    //If it is not head then simply update previous node 
                    previousNode.next = currentNode.next;
                }
                //Reduce length by 1
                this.length--;
            }

            //Previous node will point to this node with every iteration
            previousNode = currentNode;
            //Current node will point to next node for iteration
            currentNode = currentNode.next;
        }               
    }

    searchElement(value){
        let currentNode = this.head;
        while(currentNode !== null){           
            if(currentNode.value === value) return true;       
            currentNode = currentNode.next;
        }
        return false;
    }

    printList(){
        //Creates an empty array.
        let printArrayList = [];
        //Pointer which points to the head node
        let currentNode = this.head;
        //Start iterating from the first node till you reach the last node
        while(currentNode !== null){
            //Add every node's value to the array
            printArrayList.push(currentNode.value);
            //Point pointer to the next node
            currentNode = currentNode.next;
        }
        //Return the array
        return printArrayList.join(' -> ');
    }
}
console.log('Creating a LinkList at constant time O(1): 20:');
const myLinkedList = new LinkedList(20);
console.log(myLinkedList.printList());
console.log('');

console.log('Appendding Node at constant time O(1): 40 -> 50:');
myLinkedList.append(40).append(50);
console.log(myLinkedList.printList());
console.log('');

console.log('Prepending Node at constant time O(1): 10:');
myLinkedList.prepend(10);
console.log(myLinkedList.printList());
console.log('');

console.log('Inserting Node at index 2 with time complexty of O(n): 30');
myLinkedList.insert(2,30);
console.log(myLinkedList.printList());
console.log('Inserting at index 1: 15');
myLinkedList.insert(1,15);
console.log(myLinkedList.printList());
console.log('');

console.log('Deleting Head-Node at constant time O(1): 10:');
myLinkedList.deleteHead();
console.log(myLinkedList.printList());
console.log('');

console.log('Deleting Tail-Node at O(n) time: 50:');
myLinkedList.deleteTail();
console.log(myLinkedList.printList());
console.log('');

console.log('Deleting Node at index 2 with time complexty of O(n): 30:');
myLinkedList.deleteAtIndex(2);
console.log(myLinkedList.printList());
console.log('');

console.log('Deleting Node with value 40 with time complexty of O(n):');
myLinkedList.deleteNodeByValue(40);
console.log(myLinkedList.printList());
console.log('');

console.log('Searching for value 20 with time complexty of O(n):');
console.log(myLinkedList.printList());
console.log(myLinkedList.searchElement(20));
console.log('Searching for value 50 with time complexty of O(n):');
console.log(myLinkedList.searchElement(50));

Listing 21- LinkedList.js

Image 23- Final output of LinkedList.js

Summary

Today we learned what LinkedList is. What are the different operations that can be performed on LinkedList? How expensive could each operation be? Later we saw how to code those operations in javascript.

This is a single LinkedList; there are other types of LinkedList, such as doubly LinkedList and circular LinkedList. We will learn about them in upcoming articles. 

I hope you found this article helpful and helped you understand the basics of the linked list.

Happy coding, Cheers.

If you want to update the code better, feel free to fork in the following branch.

LinkedList.js