DEV Community

loading...

Linked list in javasript

Int_Shibin
Software engineer , UI enthusiast
・2 min read

Linked list as an integral part of software engineering learning has a huge impact on every engineers career. It is important to have a deep understanding of various datastructures and their ability to solve different types of problems.
Linkedlist is a linear datastructure in which each element is a seperate object. unlike array linked list is dynamic datastructure, meaning the memory allocated has flexibility to grow or shrink. Developer has the power to do that.
Linked list diffrentiated into two

  • SinglyLinkedList- which has only next property in node.
  • DoublyLinkedList- which has both next and prev property in it's node class, >dll is more flexible when it comes to the reverse traversal.

In this article we are going to use singlyLinkedList. Okey then let's dive into the concepts and implimentations.

Let us call each linked list element as node , each node has a data and a reference to next node .Last node has a reference to null.

A node 'll look like this

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

To define a linked list another class need to create

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

and a method addEl for making a connected links of these nodes. in this method we have two conditions, one to add element in empty linked list another to add element to existing linked list which has nodes.
In the later condition we need to traverse through the linked list till the last element to add a new node with a data

addEl(data){
    let newNode = new Node(data),current;
    if(!this.head){
      this.head = newNode;
    }else{
      current = this.head;
      while(current.next){
        current = current.next
      }
      current.next = newNode;
      newNode = current
    }
  }

For traversing linkedlist need to set a pivot/current node, for moving forward or backward we need to replace the current node.

Let us move on to delete operation now

deleteEl(data) {
    if (this.head == null) {
      return false;
    } else {
      let current, temp;
      current = this.head;
      if (current.data == data) {
        this.head = current.next;
      } else {
        while (current.next.data != data) {
          current = current.next;
        }
        temp = current.next;
        current.next = temp.next;
      }
      this.size--;
    }
  }

here if data passed is valid then we have to again traverse through the linkedlist to fetch the node unless we have the data available in the head itself.Once we find out the data we need to rearrange the chain by linking previous node and next node of the deleted node.

Finally we can analyse reverse operation in linked list

reverseLinkedList() {
    let nodes = [],
      current,
      node;
    current = this.head;
    while (current) {
      nodes.push(current);
      current = current.next;
    }
    let revLl = new LinkedList();
    revLl.head = nodes.pop();
    current = revLl.head;
    node = nodes.pop();
    while (node) {
      node.next = null;
      current.next = node;
      current = current.next;
      revLl.size++;
      node = nodes.pop();
    }
    return revLl;
  }

First thing we need to initialise a diffrent linkedlist and required to add elements in reverse order, for doing that i created a stack and added all my nodes to it and retreive one by one and added to the new linkedlist.

Discussion (0)