Hello, Habr Readers! Usually, when we talk about Algorithms it is hard not to mention Linked List. It is one of the main Data Structures in programming. Today we will understand how we can implement Linked List in JavaScript.

Navigation

• Implementation
• The Basic Methods
  
  1. addToTheEnd(value)
  2. insertInPosition(position, value)
  3. getNodeByPosition(position)
  4. removeFromPosition(position)
  
  
• Extra Methods
  
  1. getIndexOf(value)
  2. removeElementByValue(value)
  3. isEmpty()
  4. getLength()
  5. print()
  
  
• What about speed? Big O
• Conclusion

Implementation

The Linked List consists of Nodes. Each node comprises a value and a link to the next node in the list. In order to create it in JavaScript, we will use classes. Let's do this.

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

If you don't familiar with classes and don't understand the meaning of the code I highly recommend you to read some information about OOP (Object-oriented programming). There is a great article on the freecodecamp web-page.

So we have a Node class. Now we need to create a class for our Linked List that will contain methods for working with it. Let's initialize the constructor.

class LinkedList {
    constructor() {
        this.head = null;
        this.length = 0;
    }
}

Our constructor comprises two parameters:

• this.head — link to the first node in Linked List
• this.length — number of all nodes in Linked List

Now let's think together, what can we do with the list of elements/nodes? We can add, remove and search the nodes. These are basic functions that are the minimum for the proper work of Linked List.

Let's start by adding a Node to Linked List. We will implement 2 methods that provide this functionality.

• addToTheEnd(value) — adds Node to the end of the list
• insertAtPosition(position, value) — adds Node in specified position in the list

Adding to the end

addToTheEnd(value) {
    let node = new Node(value); //creating the node using class Node

    if (this.length === 0) {
        this.head = node; // If there are no nodes 
        // node variable will be the first and head node in the list
    } else {
        let current = this.head;

        while(current.next) {
            current = current.next;
        }

        current.next = new Node(value);
    }

    this.length++;
}

Let's analyze the difficult moments in the code above.
Note: the simple moments are described in the comments in the code.

From my perspective, the hardest thing is to understand the code in else {}. Let's analyze it step by step.

1. let current = this.head; creates the link to the head (first node) in our Linked List.
   
2. Then we go through the entire list until we get to the end of it.
   

   while(current.next) {
       current = current.next;
   }
   

   
   The end of the linked list is the Node with the link to its the next node which value equals to null. When the loop reaches the last node, the created node becomes the next node of the previous last node. current.next = new Node(value);
   
   If you look at this image below it will be easier to understand the principle of this method.
   
   
   
3. this.length++; increaments the length of our Linked List by one.
   

The next function for adding the node is insertInPosition(position, value).

insertInPosition(position, value)

It accepts two parameters:

1. position — position where we want to insert the Node.
2. value — the value for the Node to insert.

The code:

insertInPosition(position, value) {
    if (position < 0 || position > this.length) { // returns the warning message 
                                             // if incorrect position was specified
        return 'Incorrect value of position';
    }

    let node = new Node(value); // creates the node using class Node

    if (position === 0) { 
        node.next = this.head; 
        this.head = node;
    } else {
        let current = this.head;
        let prev = null;
        let index = 0;

        while (index < position) {
            prev = current;
            current = current.next;
            index++;
        }

        prev.next = node;
        node.next = current;
    }

    this.length++;
}

This method is more complex than the previous one. But this is not so difficult to understand. Let's analyze the code.

1. At first, we want to insert the node in the 0th position (the head of the list)
   

   if (position === 0) {
       node.next = this.head;
       this.head = node;
   } 
   

   
   
   • node.next = this.head; sets the current head of the list as the next element of the created node.
     
   • this.head = node; inserts the created node in the 0th position. Now our created node is the head of Linked List.
     
   
   
   
   
2. If we want to insert the node in the position which doesn't equal to 0 the code in else {} is implemented.
   
   

   else {
       let current = this.head; // link to the head node
       let prev = null; // link to the previous node. For the first element in the list it is null because it doesn't exist
       let index = 0; // varible which will be increamented to reach the specified position
   
       while (index < position) {
           prev = current;
           current = current.next;
           index++;
       }
   
       prev.next = node; 
       node.next = current;
   }
   

   
   In the while loop, we go through the Linked List until we get the specified position. Also, we move links to the previous and current nodes. When the index value becomes like the position value we insert the node in an appropriate place.
   
   
   • prev.next = node; inserts the created node in the position where another node used to be.
   • node.next = current; previous current node becomes the next node of the inserted node
   
   Look at the image below for better understanding.
   
   
   
   
3. Also we shouldn't forget to increament the length of Linked List. this.length++;

Okay, we learned how to add nodes to the Linked List. Now we need to find some of them. We will use getNodeByPosition(position) for this purpose.

getNodeByPosition(position)

getNodeByPosition(position) {
    if (position < 0 || position > this.length) { // verification of the specified position value
        return 'Incorrect value of position';
    }

    let current = this.head; // the head of the list
    let index = 0; // the index for incrementation

    while(index < position) {  // goes through each node until the index reaches the position
        current = current.next; // moves the link to the next node of the current node
        index++; // increaments the index
    }

    return current.value;
}

In the while loop, we go through each node. When the index will reach the same value as the position has the method will return the value of the searched node.
Let's look at the image below.



The last basic method for our Linked List is removeFromPosition(position).

removeFromPosition(position)

The method name speaks for itself (well, like all other method names). It must remove the node from the specified position. Let's look at the full code.

removeFromPosition(position) {
    if (position < 0 || position > this.length) { //verification on correct value of position like in the insertInPosition and getNodeByPosition
        return 'Incorrect value of position';
    }

    let current = this.head; // now current is the head of the Linked List

    if (position === 0) {
        this.head = current.next;
    } else {
        let prev = null;
        let index = 0;

        while(index < position) {
            prev = current;
            current = current.next;
            index++;
        }

        prev.next = current.next; 
    }

    this.length--;
    return current.value;
}

Let's start analyzing the code.

1. 
   

   if (position === 0) {
           this.head = current.next;
       }
   

   
   If we want to remove the node from the 0th position we just need to move the link of the head.
   
2. Then we go through the Linked List until the index reaches the position. It is the same method as in the insertInPosition(position, value).
   Here is a one difference: prev.next = current.next;. This string of code tells us that after the node in position = position — 1 will be the node with position = position + 1. It means that the node with position = position is removed. Let's look at the image explanation of this moment.
   
   
   
   
3. Also we need to decreament the length of our Linked List: this.length--;
   
4. Moreover we return the removed value of the node. We need it in order to use it in the future. return current.value;

There were the basic methods for the Linked List implementation in JavaScript. But there are many other useful ones that facilitate the work with this data structure. Let's view the most usable methods.

Extra methods

At first, we will create getIndexOf(value) method.

getIndexOf(value)

The same method exists for arrays in JavaScript: array.indexOf(value). It returns the index of element by the specified value from array. Our method getIndexOf(value) works the same way.

The full code:

getIndexOf(value) {
    let current = this.head; // current is a head of our list
    let index = 0; // index which will be returned

    while(current) {
        if (current.value === value) {
            return index;
        }
        
        current = current.next;
        index++;
    }

    return -1;
}

Code analysis of getIndexOf:

1. The code is simpler than previous ones. In the while loop, we go through each Node of Linked List. If value of the currently checking node is equal to the searching node the method returns index. Else it moves the link of the current node to the next node: current = current.next;
   
2. If the value isn't found getIndexOf(value) method will return -1.

removeElementByValue(value)

removeElementByValue is the shortest method among all in the LinkedList class. It removes the node from the list by the specified value. Let's look at the code.

removeElementByValue(value) {
    return this.removeFromPosition(this.getIndexOf(value));
}

This method uses two previous methods that we have already viewed. There are removeFromPosition and getIndexOf.

1. this.getIndexOf(value) returns the index by value
2. this.removeFromPosition(index) removes the node by specified position

isEmpty()

isEmpty() {
    return this.length === 0;
}

isEmpty() method simply checks whether our Linked List is empty or not.

getLength()

getLength() {
    return this.length;
}

getLength() method returns the number of nodes in the Linked List. That is why we incremented and decremented this.length after adding and removing the Node.
The last method in this article is related to output a linked list.

print()

print() {
    let current = this.head;

    while(current) {
        console.log(current.value); // output the value of the node
        current = current.next;
    }
}

This method simply goes through each node in the Linked List and outputs the value of each node.

Let's try it in practice

It's cool! We have written all the methods which we need for Linked List Algorithm Implementation.

You can check it out for yourself here.

What about speed?

There is a table below which displays a big O notation of each method described in the article. If you haven't ever heard about big O I recommend you to read this article on Medium.


* — beginning means position = 0.

Conclusion

You can see that the Data Structure of Linked List is not the fastest Algorithm. There are Stack, Queue, BST, etc. that work faster in some cases. But a comprehension of Linked List will make it easier for you to learn and understand other Data Structures.

Also if you are interested in Algorithms you can read my article about Quick Sort.

Moreover, if you want to plunge into algorithms learning I highly recommend you to read the book Aditya Bhargava “Grokking Algorithms”(taken from github.com/KevinOfNeu). It contains a lot of simple explanations of all popular algorithms.

My Social Networks

Twitter
GitHub
Telegram
VK