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.

Previous post Find Length Of A Linked List Iterative And Recursive
Next post Swap nodes in a linked list without swapping data

Leave a Reply

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