Easy Explanation of Linked list Data Structure in JavaScript

So we have arrived now at our next stop in the series of “Understanding Data Structure and Algorithms with JavaScript 🚀”, which is Linked List data structure in javascript. The linked list is one of the important founding blocks of data structure on which another data structure like a tree or graph is made.

In this blog, we will see the meaning, real-life examples, differences, implementation, a few common problems, and a few drawbacks related to the Linked list.

What is Linked List?

A linked list is a linear data structure made up of a sequence of connected nodes which contains a value and the address to other nodes, and the order of the data elements is not governed by the placement of memory.

Each record of the linked lists is known as a node, and each node contains a value and the address to the next node known as the next pointer or next link. The value in the known with different names like data, value, or payload.

The first node of the linked list is referred to head and the end of the node is referred to as the tail.

Difference between Linked list and Array

Array and LinkedList both are linear data structures with elements of the same data type but the major difference lies in the memory placement. Where the elements of the array are placed adjacent in the heap memory, next to each other but in LinkedList elements are placed in random locations on the heap memory, each connected through a pointer or next link.

LinkedList	Array
A linked list is an ordered collection of elements of the same type, saved at a random location on the memory.	An array is a collection of elements of the same data type, saved adjacent to each other on the memory.
Each node is connected through a link pointing to another node’s location.	Each element is placed in contiguous locations in memory.
Any elements can’t be accessed easily, elements have to be accessed sequentially.	Any random elements can be accessed easily through the index.
The insertion and Deletion process is easy and fast, as adding and removing elements means adding or removing link pointer from or to it.	The insertion and Deletion process is hard and costly, as the elements are placed in contiguous memory, and adding or removing means changing memory address.

Also read, What is Big O Notation – Space and Time Complexity

Types of Linked List

 These are some common types of linked lists:-

Singly Linked list

It is the most common type of linked list. In this type, each node has one value and the next link pointer which is pointing towards the successor node only. 

Doubly Linked list

Doubly linked list, as the name suggests, this linked list contains double-pointer. In this type, each node has one value and two next link pointers, one pointer point towards the previous node and the other to the successor node.

Circular Linked list

A circular linked list is like a single linked list but with a small variation. In this type, the tail node pointer points towards the head node of the linked list. Thus, the linked list appears to be in a circular diagram.

In this linked list there is no head or tail node, any node can be presented as a head node and we can traverse from that node.

Also read, Remembering a Programming Language that Helped Shape the Digital New York Times

Real-life like examples of Linked list

There are some real-life like examples of linked list:-

1. The simple real-life straight example of a linked list is a train. Each train car is linked together in order wise, where goods are loaded, unloaded and if any train car breaks, the link is changed and that car is removed and other end cars are attached together.
2. Opening a tab and then moving forward with the link in the tab is based on a linked list, for example, when you open a tab, it points to null and when you search something on google and open the again link, a new node is created.
3. A necklace is also like a linked list connected with each other through the link, and the node is like a diamond, and if the diamond gets damaged, then you can simply remove the node and connect the remaining links.

Also read, Simple Explanation on Searching Algorithms with JavaScript

Implementation of the Linked list in JavaScript

In order to implement a Linked list in JavaScript, first, we need to create a class called Node, Node has two properties, which store a value and reference to the next node.

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

And then we will define the Linked list class with a constructor, which saves the head node, tail node, and length of the linked list structure.

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

Also read, Understanding Array, String, and Object Data Structure with JavaScript

Few LinkedList Methods

Here are a few important linked list methods:- 

Add New Element

This method is used to add a new element to the linked list:-

// add new item
  push(val){
    let newNode = new Node(val);
    if(!this.head){
      this.head = newNode;
      this.tail = newNode;
    }else{
      this.tail.next = newNode;
      this.tail = newNode;
      this.length++
      return this
    }
  }

In the order to add a new element at the end of the list, we consider the following:-

• If the list is empty, which means if the head is null then, we add the new element and mark it as head and tail both and then increase the length by 1.
• But if a head is already present in the list (means list is not empty), then we point the tail next pointer which is null currently to the new node.

We can call the push method of the linked list like this:-

let list = new LinkedList();

for(let i = 1; i <= 5; i++){
    list.push(i)
}

Print all the Elements

This method is used to print all the elements present in the linked list:-

  // print all the elements
traverse(){ 
  let current = this.head;
  let st = "";
  while(current){ 
    st+=current.val +" -> ";
    current = current.next; 
  }
  console.log('All the elements in the linked list are:-', st+null) 
}

In the order to print all the elements present in the list, we consider the following:-

• First, we will save the head node to a variable and empty string variable st.
• then we iterate over the entire list and save each node value to the string.
• And once we get all the elements and print the final string.

Remove the last element

This method is used to remove the last element present in the linked list:-

  // remove last digit
  pop(){
    let current = this.head;
    let temp = this.head;
    while(current.next){
      temp = current;
      current = current.next
    }
    temp.next = null;
    this.tail = temp;
    this.length --;
  }

In the order to remove the last element present in the list, we consider the following:-

• We maintain two-variable, while iterating, the current variable track the last element, and the temp variable tracks the second last element. 
• then we point to the second last element to the null and mark the second last element to be the new tail.
• finally, we decrease the length by 1.

Remove the first element

This method is used to remove the first element present in the linked list:-

  // remove front node
  shift(){
    if(!this.head) return 'No Head'
    let current = this.head;
    this.head = current.next;
    this.length--;
    return this
}

In the order to remove the first element present in the list we consider the following:-

• First, we check if the head or list is empty or not and if true then return with a statement, like “No Head”.
• then we save the head node to a variable and then the head is marked to the second element of the list.
• finally, we decrease the length by 1.

Index of the element

This method is used to find the index of the element present in the linked list:-

indexOf(element){ 
  let count = 0;
  let current = this.head;
  while (current != null) {
    if (current.val === element){
      return count;
    }
     count++;
     current = current.next;          
  }
  return -1;
}

In the order to find the index of the element present in the list, we consider the following:-

• First, we will maintain a variable to keep the count of the index.
• then we iterate over the entire list and compare with each element if it is inside the list or not, if found return the index of the element.
• If not found then return -1.

Also read, Simple Explanation on Sorting Algorithms with JavaScript | Part 1

Final Words

I hope you like my article on the Linked list, and If you found this article helpful please share it more with your friends, family, and colleagues. 

And please bookmark our website, so that you can get new articles of the blog series “Understanding Data Structure and Algorithms with JavaScript 🚀” and to get more awesome articles related to business, software, and technology.