LinkedList implementation in JavaScript

In this article we will study javascript linked list implementation. A linked list is a dynamic data structure as we can add or remove nodes easily. A linked list stores data in the form of non-contiguous memory blocks in 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.

Let us look at the implementation of a javascript linked list implementation.

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

Now let’s further implement the javascript linked list implementation:

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 LinkedList in javascript. To understand better how javascript linked list implementation, I would highly recommend you solve some problems on Linked List, which our expert mentors curate at PrepBytes, you can follow this link Linked List.

FAQs related to javascript linked list implementation

1. Can we implement a linked list in javascript?
The linked list in Javascript is a data structure that stores a collection of ordered data that can only be accessed sequentially. The data element (technically a node) consists of some information and a pointer.

2. How do you create a linked list in javascript?
Javascript linked list implementation:

  • Create a function for creating a new Node object.
  • Create the LinkedList class with the proper constructor.
  • Create the insert() and print() methods.
  • Create the remove() method to remove nodes.
  • Create the methods to remove and insert from the head.

Leave a Reply

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