Introduction to Linked List

What is Linked List? 🎗️

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. For example,

image credits: programiz.com

Important Concept 🎗️

• The linked list can be used in almost every situation where a 1D array is used.
• The first node of the linked list is called head.
• The last node of the linked list is called tail.
• tail has always null as the next reference because it's the last element.
• The next is always pointing to the successor node in the list.

Types of Linked List 🎗️

Singly Linked List

In a Singly Linked List, the node has only one reference which stores the address of the next node in the list. We are going to cover it in this article.

Doubly Linked List

In Doubly Linked List, the node has two references. One to the next node and another to the previous node.

Circular Linked List

In Circular Linked List, the node may have one or two references. But the tail will be connected to the head of the Linked List.

Time Complexity 🎗️

Space Complexity of Linked List: O(n)

Applications of Linked List 🎗️

1. Linked List is heavily used to create stacks and queues.
2. When you need constant-time insertions or deletions from the list.
3. When the size of the list is unknown. This means you don't know how much your list is going to be scaled, then use Linked List instead of Arrays.
4. To implement Hash Tables, Trees or Graphs

Advantages of Linked List 🎗️

1. Using linked list efficient memory utilization can be achieved since the size of linked list can be change at the run time.
2. Stacks and queues are often easily implemented using a linked list.
3. Insertion and deletion are quite easier in the linked list.

Disadvantages of Linked List 🎗️

1. More memory is required in the linked list compared to an array.
2. Traversal in linked list is more time consuming.
3. In a singly linked list reverse traversing is not possible, but it can be done using doubly linked list which will take even more memory.
4. Random access is not possible due to its dynamic memory allocation.

Coding a Linked List in JavaScript 🎗️

At first a node class should be created which is going to represent a node in the linked list.

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

We have created a Node class and inside the constructor, we have two parameters which are the properties of a node.

1. value - It is the value of the node.
2. next - This will contain the reference of the next node. Initially, it is always null.

After creating the structure of the node, we can now create the linked list. Let's create a LinkedList class that will contain the operations of our linked list.

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

We have created a class LinkedList and inside the constructor, we are initializing three things.

1. head: The first node of the linked list.
2. tail: The last node of the linked list.
3. length: The length of the linked list.

✅ Let's code some operations of the linked list!

push

In push, we insert a node at the end of the linked list.

The steps which we are going to follow while coding push.

1. Create push function in the class that accepts a value as an argument.
2. Create a new node using the Node class while passing the value.
3. Check if the list is empty:
   • If the list is empty, then assign the new node to the head and tail. Since there is only one node which is both the head and tail in the list.
4. If the list is not empty:
   • Assign the next property of the current tail to the new node.
   • Assign the new node to the tail itself.
   • Increment the length by one.

push( value ) {
    // create node
    let node = new Node( value );

    /** check if list is empty */
    if( !this.head ) { // if empty
        this.head = node; // new head
        this.tail = node; // new tail
    } else {
        this.tail.next = node; // reference to the new node
        this.tail = node; // update the tail to the new node
    }

    this.length++;
    return this;
}

pop

In pop, we delete a node from the end of the linked list.

Here are the steps which we are going to follow while coding pop.

1. Create pop function in the class that accepts nothing.
2. Check if the list is empty:
   • If the list is empty, then return
3. If the list is not empty:
   • We have to calculate second last element so that we can set tail of the linked list to the second last element and remove the last one by setting the next property to null on the current tail.
   • Decrement the length by one.
   • If the length of the linked list is zero, that means the linked list is empty. So we set the head and tail to null.

pop() {

    // if head is null, then return null
    if( !this.head ) {
        return;
    }

    // find the second last node.
    let currentNode = this.head,
        secondLastNode;

    while( currentNode.next ) {
        secondLastNode = currentNode;
        currentNode = currentNode.next;
    }

    // set the second last node to the new tail of the linked list.
    this.tail = secondLastNode;
    // set the current tail's next to null
    this.tail.next = null;
    this.length--;

    // if the length of linked list becomes 0, then reset the linked list
    if( this.length === 0 ) {
        this.head = null;
        this.tail = null;
    }

    return this;
}

shift

In shift, we remove a node at the start of the linked list.

Here are the steps which we are going to follow while coding shift.

1. Create a function shift in the class which is going to accept nothing.
2. Check if the list is empty:
   • If the list is empty, then return.
3. If the list is not empty:
   • We store the current head in a variable called removeHead.
   • We will set the current head to the next of the removeHead.
   • Decrement the length by one.
   • If the length of the linked list is zero, that means the linked list is empty. So we set the head and tail to null.

shift() {
    // If there is no head then return
    if( !this.head ) {
        return;
    }

    // change the current head
    let removeHead = this.head;
    this.head = removeHead.next;
    this.length--;

    // if the length of linked list becomes 0, then reset the linked list
    if( this.length === 0 ) {
        this.head = null;
        this.tail = null;
    }

    return this;
}

unshift

In unshift, we add a node at the start of the linked list.

Here are the steps which we are going to follow while coding unshift.

1. Create a method unshift in the class which is going to accept the value of the node as argument.
2. Creating a new node from the Node class while passing the value.
3. Check if the list is empty:
   • If the list is empty, then assign the new node to the head and tail. Since there is only one node which is both the head and tail in the list.
4. If the list is not empty:
   • Assign the next property of the current head to the new node.
   • Assign the new node to the head itself.
   • Increment the length by one.

unshift( value ) {
    // create node
    let node = new Node( value );

    /** check if list is empty */
    if( !this.head ) { // if empty
        this.head = node;
        this.tail = node;
    } else {
        node.next = this.head;
        this.head = node
    }

    this.length++;
    return this;
}

All this time we only added or removed nodes from either the start or the end of the linked list. For which we didn't have to do extra amount of work to find the position. If we want to add, delete or update nodes at a given position then it becomes a necessity to find positions of nodes in a Linked List.

findNode

In findNode, we find a node at a given index of the linked list.

Here are the steps which we are going to follow while coding findNode.

1. Create a method findNode in the class which is going to accept the index of the node which we want to find.
2. Checking whether the index is negative or out of bound. If so then return null.
3. We traverse through the linked list until we find the node at the given index, if found we return the node else null.

findNode( index ){
    if( index < 0 || index >= this.length ) {
        return null;
    }

    let counter = 0,
        node = this.head;

    while( node ) {
        if( counter === index ) {
            // returns node at given index.
            return node;
        }
        counter++;
        node = node.next;
    }

    return null;
}

updateNode

In updateNode, we find a node at a given index of the linked list and update the value of the node.

Here are the steps which we are going to follow while coding updateNode.

1. Create a method updateNode in the class which is going to accept the index of the Linked List as an argument.
2. If index is negative or out of bound then return false.
3. If not then:
   • Storing the node of our desired index which we will find from findNode function.
   • Assign the data which we want to update to the property called value of the node.
   • After updating the node we return.

updateNode( data, index ) {
    if( !this.findNode( index ) ) {
        // returns false on negative index or out of bound.
        return false;
    } else {
        let node = this.findNode( index );
        node.value = data;

        // updates node and returns true
        return this;
    }
}

deleteNode

In deleteNode, we delete a node at any given index of the linked list.

Here are the steps which we are going to follow while coding deleteNode.

1. Create a method deleteNode in the class which is going to accept the index of the Linked List as an argument.
2. If index is negative or out of bound then return.
3. If the index is equal to zero then we will use shift function.
4. If not then:
   • Storing the node of our desired index which we will find from findNode function.
   • After that we storing previous node using the same findNode function.
   • Assign the next of the previous node to the next of the node that we want to delete.
   • The length of the Linked List is decreased by one.

deleteNode( data, index ) {
    if( !this.findNode( index ) ) {
        // returns false on negative index or out of bound.
        return false;
    } else {
        let node = this.findNode( index ),
            prevNode = this.findNode( index - 1 );

        prevNode.next = node.next;
        this.length--;

        // removes and returns node at given index
        return this;
    }
}

insert

In insert function, we insert a node at any given index of the linked list.

Here are the steps which we are going to follow while coding insert.

1. Create a method insert in the class which is going to accept the index of the Linked List as an argument.
2. If index is negative or out of bound then return.
3. If the index is equal to zero then we will use unshift function.
4. If not then:
   • We store the node of our desired index in nextNode variable and its previous node in prevNode using the findNode function.
   • We create a new node where its next is the address of the node stored in nextNode and connect the new node by storing its address in the next of the node in prevNode variable.
   • The length of the Linked List is increased by one.

insert( data, index ) {
    if( index < 0 || index >= this.length ){
        // returns false if the index is negative or out of bound.
        return false;
    }
    if( index === 0 ) {
        this.unshift(data);
        return this;
    }

    let prevNode = this.findNode( index - 1 ),
        nextNode = this.findNode( index );

    prevNode.next = new Node(data, nextNode);
    this.length++;

    // removes and returns node at given index
    return this;
}

Conclusion 🎗️

In this blog, we covered the fundamentals of Linked List. Its applications, advantages and disadvantages. We learned how to add or delete nodes to/from starting and ending of a linked list. We also learned how to find a node in the Linked List at a given index. And finally, we learned how to add, delete or update node at a given index.

Wrap Up 🎗️

Thank you for reading.

If you find this helpful, leave a like, share, and follow me, @srafsan to read more articles.