How to create a singly linked list in JavaScript

#javascript #beginners #tutorial

JavaScript comes with some out of the box data structures. This includes Arrays and objects. Linked List, graphs, trees, queues, and stacks are not included with JavaScript. these data structures need to be constructed using a class. The data structures mention are important to know since different data structures excel at storing and retrieving data more efficiently than others depending on the scenario.

What is a singly linked list?

A singly linked list is a data structure that consists of a head, tail, and length property. The head and tail are assigned a node object. The singly-linked list can only be traverse in one direction. Starting at the head and ending at the tail.

What does a singly linked list contain and how to build it?

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

class SinglyLinkedList{
    constructor(value){
        this.head = new Node(value);
        this.tail = this.head; 
        this.length = 1; 
    }
}

const newSinlglyLinkedList = new SinglyLinkedList(1);

To get started building a singly linked list we first need to create 2 classes. The first class will create node objects which contain a value and a next property. The second class is the Singly linked list which contains a head, tail, and length. When we first instantiate a singly linked list a new node is created and is set to the head and tail properties of the linked list.

Append

    //adds to the end of the linked list
    append(value){
        const newNode = new Node(value); 
        // set the next property of the tail to the new created node
        this.tail.next = newNode; 
        // set the tail equals to the new node
        this.tail = newNode;
        this.length++; 
        return this; 
    }

The first instance method that will be covered is append. Append takes in a value as a parameter. Append adds nodes to the end of the linked list. First, we need to create a new node, attach the new node to the linked list by setting the next property on the tail to the new node, set the new node as the tail, and finally increase the length.

Prepend

    prepend(value){
        const newNode = new Node(value);
        newNode.next = this.head;
        this.head = newNode;
        this.length++
        return this; 
    }

The instance method prepend works similarly as append. Prepend takes in a value as a parameter. The new node will be added at the beginning of the linked list. The new node is created the next property on the new node is set to the head, the head is set to the new node, and the length is increased.

Traverse

    traverse(index){
        if(index > this.length - 1){
            index = this.length -1;
        }
        if(index < 0){
            index = 0
        }
        let currentNode = this.head; 
        let i = 0;
        while(i < this.length){
            if(i === index) return currentNode; 
            currentNode = currentNode.next; 
            i++
        }
    }

A helper function is needed to write the rest of the missing methods for the linked list. We will call this function transverse. This function takes in an index and returns the current node at that index. First, a couple of checks to see if the index pass is within range. Second, we use a while loop to transverse each node using their next property and checking to see if the variable i and index are equal. If there is a match return the currentNode.

Insertion

    insert(index, value){
        // need to check if the node we are inserting is at the begining.
        if(index < 0 ){
            index = 0;
        }
        if(index === 0){
            return this.prepend(value);
        }
        // need to check if node we are inserting is at the end
        if(index > this.length - 1){
            return this.append(value);
        }
        // else is not at the end or beggining
        // create a previousNode, newNode, currentNode
        const previousNode = this.transverse(index - 1)
        const newNode = new Node(value);
        const currentNode = this.transverse(index)
        // assing newNode  pointer to the currentNode; 
        newNode.next = currentNode; 
        // assing previousNode pointer to the newNode; 
        previousNode.next = newNode;
        this.length++
        return this;  

    }

Insertion is a bit trickier than the two other instance methods. Insert takes in two parameters a value and an index where the insert will take place. First, a check to make sure the index pass is not lesser than zero. If the index is equal to zero we want to use our prepend method to add to the beginning and if the index is greater than the length minus one than we want to append. That covers those scenarios. Now to take care of inserts in the middle on the linked list. we require a new node, a current node, and a previous node. We will use the transverse method to add collect the nodes. The next property of the newNode is set to currentNode and the previousNode next property is set to the new node. The length is increased and that concludes the insert method.

Delete

    delete(index){
        //check if index is out of bounds
        if(index > this.length - 1){
            index = this.length - 1; 
        }
        if(index < 0){
            index = 0; 
        }
        // create all the nodes you will need 
        const prevNode = this.transverse(index - 1);
        const currentNode = this.transverse(index);
        const nextNode = this.transverse(index + 1);
        if(index === 0){
            currentNode.next = null; 
            this.head = nextNode;
        } else if(index === this.length -1){
            prevNode.next = null; 
            this.tail = prevNode;
        } else {
            currentNode.next = null; 
            prevNode.next = nextNode; 
        }
        this.length--
        return this;
    }

The delete method will only take in the index of the node that will be deleted. The index value is checked to see if it is within range. Next, we will collect all the nodes require for the reverse method to work. If the index is equal to zero, the currentNode next property is set to null. This cuts the node off the linked List. The nextNode is set to the head. If the index points to the tail in the linked list, the prevNode next value is set to null and the tail is set to the prevNode. If the index is not pointing to the first or last node then the currentNode next property is set to null and prevNode.next is set to the nextNode. Finally, the length is decreased.

Why use a singly linked list?

You might be wondering what is the point of using a singly linked list. The singly-linked list has an order and has really fast prepend, append, and deletes (index of zero) instance methods. The Time complexity of the append, prepend, and deletions at the index of zero are constant time. This data structure works great if you are trying to build a queue (First In First Out). A queue can be implemented with an array but, it can be very inefficient. Following the FIFO rule we can use an arr.push() method to insert values into an empty array and arr.shift() to remove them. arr.shif() is very inefficient. (linear time) this is because removing a value from the beginning of the array will require shifting of all the index in the array. A better way to create a queue is by using a singly linked list. We can use append to add values to the end and use delete with an index of zero to remove the first value in the queue. Using both of these methods we can make a queue that has a time complexity of constant time.

I hope this helps you understand how to create your own linked list and their purpose. Visualizing algorithms and data structures can give you an idea of how to build them. Here is a great resource for that https://visualgo.net/en.