LinkedList implementation in JavaScript

Introduction

A linked list is a linear data structure, which stores data in the form of non-contiguous memory blocks in the memory. It is similar to an array as it is linear but offers dynamic size.

A node of a linked list needs to store at least $2$ information:
1) The data stored in the node
2) The pointer to the next node

While creating a new node, we can initialize its value with the value passed and next as null.

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

Now let’s further implement the linked list:

push_front(x)

push_front(x) will add a new node containing the value as x, to the front of the linked list and the head will be updated to point to this new node.

push_front(x){
    let node = new Node(x);
    node.next = this.head;
    this.head = node;
    this.size ++;
}

push_back(x)

push_back(x) will add a new node with value x at the end of the linked list

  • If the linked list is empty, then push_back will be the same as push_front and the new node will be the head node.
  • Else we traverse till the last node and add a new node there
push_back(x){
    if(this.head==null){
        push_front(x);
        return;
    }

    // reach the node just before the end
    let curr = this.head;
    while(curr.next!==null){
        curr = curr.next;
    }

    // now curr node is the last node
    // add a new node here
    let node = new Node(x);
    curr.next = node;
    this.size ++;
}

pop_front()

pop_front() will remove and return the value in the node at the front of the linked list. If the linked list is empty, then this function will return null.

pop_front(){
    // if linked list is empty
    if(this.head === null) return null;
    
    // store the front node in temp
    let temp = this.head;

    // modify the head to point to the next node
    this.head = this.head.next;
        
    // decrease size of linked list
    this.size --;
    
    // return the value in temp
    return temp.val;
}

pop_back()

pop_back() will remove and return the value in the node at the end of the linked list. If the linked list is empty, this function will return null.

pop_back(){
    if(this.head === null) return null;
        
    // reach the node just before the end
    let curr = this.head;
    while(curr.next!==null){
        curr = curr.next;
    }
    let back = curr.val;

    // to disconnect the last node 
    // set the next pointer of node just before
    // the last node as null
    curr.next = null;
    this.size --;
    
    return back;
}

Implementation of linkedList class along with all above functionalities

class linkedList {
    constructor(){
        this.head = null;
        this.size = 0;
    }
    
    // to add an element x at the front of the linked list
    push_front(x){
        let node = new Node(x);
        node.next = this.head;
        this.head = node;
        this.size ++;
    }

    // to add an element at the back of the linked list
    push_back(x){
        if(this.head==null){
            push_front(x);
            return;
        }

        let node = new Node(x);

        let curr = this.head;
        while(curr.next!==null){
            curr = curr.next;
        }
        curr.next = node;
        this.size ++;
    }

    // to remove and return an element which is at the front of
     // the linked list
    pop_front(){
        if(this.head === null) return null;
        let temp = this.head;
        this.head = this.head.next;
        this.size --;
        return temp.val;
    }

    // to remove and return an element from the back of 
     // the linked list
    pop_back(){
        if(this.head===null) return null;
        let curr = this.head;
        while(curr.next!==null){
            curr = curr.next;
        }
        let back = curr.val;
        curr.next = null;
        this.size --;
        return back;
    }

    // to find out whether the linked list is empty or not
    isEmpty(){
        return this.size === 0;
    }

    // to find out the size of the linked list
    getSize(){
        return this.size;
    }

    // to print the linked list
    printIt(){
        let temp = this.head;
        let s = "";
        while(temp !== null){
            s += temp.val + " ";
            temp = temp.next;
        }
        console.log(s);
    }
    
    // to find out the position of an element x in 
     // the linked list
    positionOf(x){
        let temp = this.head;
        let pos = 1;
        while(temp !== null){
            if(temp.val === x){
                return pos;
            }
            temp = temp.next;
            pos ++;
        }
        
        // if x isn't found
        return -1;
    }
}

In this article, we understood how to implement a linear data structure called a linked list in JavaScript. To understand it better, I would highly recommend you to solve some problems on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Leave a Reply

Your email address will not be published. Required fields are marked *