Linked list data structure in javascript

We will see why we need to use linked list over arrays and implement an object based linked list data structure in javascript.

Why do we need linked list?

Arrays are the most common data structures that are used to store collection of data.

This however has some disadvantages

  • Arrays in most programming languages are of fixed length, so it is really not easy to store data beyond its size.
  • Also adding and removing element in the middle of the array is expensive because we have to shift all the other elements in the array.
  • In javascript, arrays are flexible but they are not efficient. They are just objects with some extra features which make them feel like an array, This makes them really slow to work with.

If we want to random access any element then arrays are the best choice else we can probably use linked list anywhere an array can be used.

What is linked list?

Linked list stores the collection of data, but unlike arrays data are not stored in contagious memory, instead each element in the linked list consists of a node which stores the data and a reference(pointer or link) to the next element.

Have a look at the following figure for better understanding.
Linked List

There are two ends to the linked list head and tail.

  • head: Represent the elements from the beginning of the list.
  • tail: Represent the elements from the end of the list.

Advantage

  • We can dynamically increase the size of the list and store any amount of data.
  • We don’t have to shift elements while adding or removing element from the middle of the list. We can just change the reference to other element.

Disadvantage

  • Every time we need to search for any data in the list we will need iterate from the start or (Head) till the desired element.
  • We will be storing the reference to the next element, so we need to pay extra attention to make things work properly.

Examples of linked list

There are many examples of linked list in real life like.

  • Scavenger hunt game where you have a clue and this clue has a reference to the other clues and thus to the treasure.
  • A train where all the wagons are linked to each other. We can easily remove and add new wagons to the train or change their position.

Now I am sure you have got a good idea about what is a linked list so lets start implementing it in javascript.

We will use modern ESNext features and implement the linked list with function as well as with Class.

List of operations performed on linked list

  • append(element): Adds a new element in the list.
  • removeAt(position): Removes an element from the given position in the list and returns it.
  • insert(position, element): Adds an element at the given position in the list.
  • toString(): Joins all the elements of the list and returns it as a string.
  • toArray(): Converts the linked list to the array and returns it.
  • indexOf(element): Returns the position of the given element in the list.
  • delete(element): Removes the given element from the list.
  • deleteHead(): Removes the first element from the list.
  • deleteTail(): Removes the last element from the list.
  • isPresent(element): Returns true if element is present in the list, false otherwise.
  • isEmpty(): Returns true if the list is empty, false otherwise.
  • size(): Returns the size of the list.
  • getHead(): Returns the whole list.

Creating a linked list data structure in javascript

We will use a Node which will be storing the element and the reference to the next element.

function linkedlist() {
  //Node 
  let Node = function(elm) {
    this.element = elm;
    this.next = null;
  }

  //To keep track of the size    
  let length = 0; 
  
  //To keep track of the list
  let head = null; 

  //Other methods go here
}

Adding an item in the linked list

We will check if head is empty then assign the current node to it, else add the node as a reference of the next element to the previous node.
Adding new item in the linked list

//Add new item in the linkedlist
this.append = function(elm) {
  let node = new Node(elm),
  current;
  
  //If head is empty then 
  //Add the node at the beginning
  if(head === null){
    head = node;
  }else{
    //Else add the node as the
    //Next element of the existing list
    current = head;
    while(current.next){
      current = current.next;
    }

    current.next = node;
  }
  
  //Increase the length
  length++;
};

Removing an item from the given position in the linked list

If the element is at the beginning of the list then just simply update the head to point to the next element in the list.
Remove the item from the beginning in the linked list

Else we will have to iterate in the list and make the previous node of the element at the given position to point to the next node of the element.

//Remove item from any position
this.removeAt = function(pos){
   if(pos > -1 && pos < length){
     let current = head,
     previous, index = 0;
     
     //If removing the first element 
     //then simply point to the next element
     if(pos === 0){
        head = current.next;
      }else{
        //Else find the correct pos 
        //and then remove the element.
        while(index++ < pos){
          previous = current;
          current = current.next;
        }

        previous.next = current.next;
      }

      length--;
      return current.element;
    }else{
      return null;
    }
 };

Insert element at the given position in the linked list

Adding the element at the beginning

If we are adding the element at the beginning i.e at the head, then just simply assign the existing list to the new node.
Adding new node at the beginning of the linked list

Adding the element in the middle

If we are adding the element in the middle of the list then we will need to iterate till the given position and then make the current node to point to the new node and new node to point at the next node.
Adding new element in the middle of the list

Adding the element at the end of the list

If we are adding the element to end of the list i.e at the tail, then we will need to iterate till the last element in the list and then make it point to the new node.
Adding element at the end of the list

  //Add item at any position
  this.insert = function(pos, elm){
    if(pos >= 0 && pos <= length){
      let node = new Node(elm),
      current = head,
      previous, index = 0;

      if(pos === 0){
        node.next = current;
        head = node;
      }else{
        while(index++ < pos){
          previous = current;
          current = current.next;
        } 

        node.next = current;
        previous.next = node;
      }

      length++;
      return true;
    }else{
      return false;
    }
  };

Getting the index of the element in the list

We will be returning the zero based index for linked list elements just like arrays, If element is not present then we will return -1.

//Get the indexOf item 
this.indexOf = function(elm){
  let current = head,
  index = -1;
  
  //If element found then return its position
  while(current){
    if(elm === current.element){
       return ++index;
    }

     index++;
     current = current.next;
   }
  
  //Else return -1
  return -1;
};

Check if element is present in the list

We can store any type of data in linked list in javascript but here we are only finding the data for String and Numeric type.

//Find the item in the list
this.isPresent = (elm) => {
  return this.indexOf(elm) !== -1;
};

Delete element from the list

//Delete an item from the list
this.delete = (elm) => {
   return this.removeAt(this.indexOf(elm));
};  

Delete the first element from the list

Removing the element from the head will remove the first element from the linked list.
Remove the item from the beginning in the linked list

//Delete first item from the list
this.deleteHead = function(){
  let current = head;
      
  if(current === null){
    return true;
  }
      
  if(current.next){
    current = current.next;
    head = current;       
  }else{
    head = null;
  }
      
  return true;
}

Delete the last element from the list

Removing the element from the tail will remove the last element from the linked list.
Remove the last element from the linked list

//Delete last item from the list
this.deleteTail = function(){
let current = head;
      
 if(current === null){
   return true;
 }
      
 while(current.next){
   if(!current.next.next){
      current.next = null;
    }else{
      current = current.next;
    }
 }
      
  return true;
}

Return the list as a string

We will concatenate all the elements of the list together and return them as a string.

//Print item of the string
this.toString = function(){
  let current = head,
  string = '';

  while(current){
    string += current.element + (current.next ? '\n' : '');
    current = current.next;
  }

  return string;
};

Return the list as an array

We will push all the elements of the list to the array and return it.

//Convert list to array
this.toArray = function(){
  let arr = [],
  current = head;
      
  while(current){
    arr.push(current.element);
    current = current.next;
  }
      
  return arr;
};

Check if list is empty

//Check if list is empty
this.isEmpty = function(){
  return length === 0;
};

Get the size of the list

//Get the size of the list
this.size = function(){
  return length;
}

Get the head of the list

//Get the head of the list
this.getHead = function(){
  return head;
}

Complete code of the linked list

function linkedlist() {
  //Node 
  let Node = function(elm) {
    this.element = elm;
    this.next = null;
  }

  //To keep track of the size    
  let length = 0; 
  
  //To keep track of the list
  let head = null; 

  //Other methods go here
  //Add new item in the linkedlist
    this.append = function(elm) {
      let node = new Node(elm),
          current;

      if(head === null){
        head = node;
      }else{
        current = head;
        while(current.next){
          current = current.next;
        }

        current.next = node;
      }

      length++;
    };

    //Remove item from any position
    this.removeAt = function(pos){
      if(pos > -1 && pos < length){
        let current = head,
            previous, index = 0;

        if(pos === 0){
          head = current.next;
        }else{
          while(index++ < pos){
            previous = current;
            current = current.next;
          }

          previous.next = current.next;
        }

        length--;
        return current.element;
      }else{
        return null;
      }
    };

    //Add item at any position
    this.insert = function(pos, elm){
      if(pos >= 0 && pos <= length){
        let node = new Node(elm),
            current = head,
            previous, index = 0;

        if(pos === 0){
          node.next = current;
          head = node;
        }else{
          while(index++ < pos){
            previous = current;
            current = current.next;
          } 

          node.next = current;
          previous.next = node;
        }

        length++;
        return true;
      }else{
        return false;
      }
    };

    //Print item of the string
    this.toString = function(){
      let current = head,
          string = '';

      while(current){
        string += current.element + (current.next ? '\n' : '');
        current = current.next;
      }

      return string;
    };

    //Convert list to array
    this.toArray = function(){
      let arr = [],
          current = head;

      while(current){
        arr.push(current.element);
        current = current.next;
      }

      return arr;
    };

    //Get the indexOf item 
    this.indexOf = function(elm){
      let current = head,
          index = -1;

      while(current){
        if(elm === current.element){
          return ++index;
        }

        index++;
        current = current.next;
      }

      return -1;
    };

    //Delete an item from the list
    this.delete = (elm) => {
      return this.removeAt(this.indexOf(elm));
    };    

    //Delete first item from the list
    this.deleteHead = function(){
      let current = head;

      if(current === null){
        return true;
      }

      if(current.next){
        current = current.next;
        head = current;       
      }else{
        head = null;
      }

      return true;
    }

    //Delete last item from the list
    this.deleteTail = function(){
      let current = head;

      if(current === null){
        return true;
      }

      while(current.next){
        if(!current.next.next){
          current.next = null;
        }else{
          current = current.next;
        }
      }

      return true;
    }

    //Find the item in the list
    this.isPresent = (elm) => {
      return this.indexOf(elm) !== -1;
    };


    //Check if list is empty
    this.isEmpty = function(){
      return length === 0;
    };

    //Get the size of the list
    this.size = function(){
      return length;
    }

    //Get the head of the list
    this.getHead = function(){
      return head;
    }
}
Input:
let ll = new linkedlist();
ll.append('prashant');
ll.append('anil');
ll.append('29');
console.log(ll.toArray());

//Remove 'anil' from the list
ll.removeAt(1);
console.log(ll.toArray()); 

//Remove the first element from the list
ll.deleteHead();
console.log(ll.toArray());

Output:
["prashant", "anil", "29"]
["prashant", "29"]
["29"]

Making the properties and methods private with closure and IIFE (Immediately Invoked Function Expression).

let LinkedList = (function(){
  //Return the function
  return function linkedlist() {
    
    //Node class
    let Node = function(elm) {
      this.element = elm;
      this.next = null;
    }

    let length = 0;
    let head = null;
    
    //Add new item in the linkedlist
    this.append = function(elm) {
      let node = new Node(elm),
          current;

      if(head === null){
        head = node;
      }else{
        current = head;
        while(current.next){
          current = current.next;
        }

        current.next = node;
      }

      length++;
    };

    //Remove item from any position
    this.removeAt = function(pos){
      if(pos > -1 && pos < length){
        let current = head,
            previous, index = 0;

        if(pos === 0){
          head = current.next;
        }else{
          while(index++ < pos){
            previous = current;
            current = current.next;
          }

          previous.next = current.next;
        }

        length--;
        return current.element;
      }else{
        return null;
      }
    };
    //Add item at any position
    this.insert = function(pos, elm){
      if(pos >= 0 && pos <= length){
        let node = new Node(elm),
            current = head,
            previous, index = 0;

        if(pos === 0){
          node.next = current;
          head = node;
        }else{
          while(index++ < pos){
            previous = current;
            current = current.next;
          } 

          node.next = current;
          previous.next = node;
        }

        length++;
        return true;
      }else{
        return false;
      }
    };

    //Print item of the string
    this.toString = function(){
      let current = head,
          string = '';

      while(current){
        string += current.element + (current.next ? '\n' : '');
        current = current.next;
      }

      return string;
    };

    //Convert list to array
    this.toArray = function(){
      let arr = [],
          current = head;

      while(current){
        arr.push(current.element);
        current = current.next;
      }

      return arr;
    };

    //Get the indexOf item 
    this.indexOf = function(elm){
      let current = head,
          index = -1;

      while(current){
        if(elm === current.element){
          return ++index;
        }

        index++;
        current = current.next;
      }

      return -1;
    };

    //Delete an item from the list
    this.delete = (elm) => {
      return this.removeAt(this.indexOf(elm));
    };    

    //Delete first item from the list
    this.deleteHead = function(){
      let current = head;

      if(current === null){
        return true;
      }

      if(current.next){
        current = current.next;
        head = current;       
      }else{
        head = null;
      }

      return true;
    }

    //Delete last item from the list
    this.deleteTail = function(){
      let current = head;

      if(current === null){
        return true;
      }

      while(current.next){
        if(!current.next.next){
          current.next = null;
        }else{
          current = current.next;
        }
      }

      return true;
    }

    //Find the item in the list
    this.isPresent = (elm) => {
      return this.indexOf(elm) !== -1;
    };


    //Check if list is empty
    this.isEmpty = function(){
      return length === 0;
    };

    //Get the size of the list
    this.size = function(){
      return length;
    }

    //Get the head of the list
    this.getHead = function(){
      return head;
    }
  }
})();
Input:
let ll = new LinkedList();
ll.append('prashant');
ll.append('anil');
ll.append('29');
console.log(ll.toArray());

//Remove 'anil' from the list
ll.removeAt(1);
console.log(ll.toArray()); 

//Remove the first element from the list
ll.deleteHead();
console.log(ll.toArray());

Output:
["prashant", "anil", "29"]
["prashant", "29"]
["29"]

Class based implementation of linked list data structure in javascript

We will be using two different classes, one for node and another one for linked list.

//Node
class Node{
  constructor(elm, next = null){
    this.element = elm;
    this.next = next;
  }
}

//LinkedList
class LinkedList{
  constructor(){
    this.length = 0;
    this.head = null;
  }
  
  //Add new item in the linkedlist
  append = function(elm) {
    let node = new Node(elm),
    current;

    if(this.head === null){
      this.head = node;
    }else{
      current = this.head;
      while(current.next){
        current = current.next;
      }

      current.next = node;
    }

    this.length++;
  };

  //Remove item from any position
  removeAt = function(pos){
    if(pos > -1 && pos < this.length){
      let current = this.head,
      previous, index = 0;

      if(pos === 0){
        this.head = current.next;
      }else{
        while(index++ < pos){
          previous = current;
          current = current.next;
        }

        previous.next = current.next;
      }

      this.length--;
      return current.element;
    }else{
      return null;
    }
  };

  //Add item at any position
  insert = function(pos, elm){
    if(pos >= 0 && pos <= this.length){
      let node = new Node(elm),
          current = this.head,
          previous,
          index = 0;

      if(pos === 0){
        node.next = current;
        this.head = node;
      }else{
        while(index++ < pos){
          previous = current;
          current = current.next;
        } 

        node.next = current;
        previous.next = node;
      }

      this.length++;
      return true;
    }else{
      return false;
    }
  };

  //Print item of the string
  toString = function(){
      let current = this.head,
      string = '';

      while(current){
        string += current.element + (current.next ? '\n' : '');
        current = current.next;
      }

      return string;
    };
    
    //Convert list to array
    toArray = function(){
      let arr = [],
      current = this.head;
      
      while(current){
        arr.push(current.element);
        current = current.next;
      }
      
      return arr;
    };
    
    //Get the indexOf item 
    indexOf = function(elm){
      let current = this.head,
      index = -1;

      while(current){
        if(elm === current.element){
          return ++index;
        }

        index++;
        current = current.next;
      }

      return -1;
    };
    
    //Delete an item from the list
    delete = (elm) => {
      return this.removeAt(this.indexOf(elm));
    };    

    //Delete first item from the list
    deleteHead = function(){
      let current = this.head;
      
      if(current === null){
        return true;
      }
      
      if(current.next){
        current = current.next;
        this.head = current;       
      }else{
        this.head = null;
      }
      
      return true;
    }

    //Delete last item from the list
    deleteTail = function(){
      let current = this.head;
      
      if(current === null){
        return true;
      }
      
      while(current.next){
        if(!current.next.next){
          current.next = null;
        }else{
          current = current.next;
        }
      }
      
      return true;
    }

    //Find the item in the list
    isPresent = (elm) => {
      return this.indexOf(elm) !== -1;
    };
    
    
    //Check if list is empty
    isEmpty = function(){
      return this.length === 0;
    };
    
    //Get the size of the list
    size = function(){
      return this.length;
    }
    
    //Get the head of the list
    getHead = function(){
      return this.head;
    }
}
Input:
let ll = new LinkedList();
ll.append('prashant');
ll.append('anil');
ll.append('29');
console.log(ll.toArray());

//Remove 'anil' from the list
ll.removeAt(1);
console.log(ll.toArray()); 

//Remove the first element from the list
ll.deleteHead();
console.log(ll.toArray());

Output:
["prashant", "anil", "29"]
["prashant", "29"]
["29"]

Making this class private with closure and IIFE

let LinkedList = (function(){
  //Node
  class Node{
    constructor(elm, next = null){
      this.element = elm;
      this.next = next;
    }
  }
  
  //Return the linked list
  return class linkedlist{
    constructor(){
      this.length = 0;
      this.head = null;
    }

    //Add new item in the linkedlist
    append = function(elm) {
      let node = new Node(elm),
      current;

      if(this.head === null){
        this.head = node;
      }else{
        current = this.head;
        while(current.next){
          current = current.next;
        }

        current.next = node;
      }

      this.length++;
    };

    //Remove item from any position
    removeAt = function(pos){
      if(pos > -1 && pos < this.length){
        let current = this.head,
        previous, index = 0;

        if(pos === 0){
          this.head = current.next;
        }else{
          while(index++ < pos){
            previous = current;
            current = current.next;
          }

          previous.next = current.next;
        }

        this.length--;
        return current.element;
      }else{
        return null;
      }
    };

    //Add item at any position
    insert = function(pos, elm){
      if(pos >= 0 && pos <= this.length){
        let node = new Node(elm),
            current = this.head,
            previous,
            index = 0;

        if(pos === 0){
          node.next = current;
          this.head = node;
        }else{
          while(index++ < pos){
            previous = current;
            current = current.next;
          } 

          node.next = current;
          previous.next = node;
        }

        this.length++;
        return true;
      }else{
        return false;
      }
    };

    //Print item of the string
    toString = function(){
        let current = this.head,
        string = '';

        while(current){
          string += current.element + (current.next ? '\n' : '');
          current = current.next;
        }

        return string;
      };

      //Convert list to array
      toArray = function(){
        let arr = [],
        current = this.head;

        while(current){
          arr.push(current.element);
          current = current.next;
        }

        return arr;
      };

      //Get the indexOf item 
      indexOf = function(elm){
        let current = this.head,
        index = -1;

        while(current){
          if(elm === current.element){
            return ++index;
          }

          index++;
          current = current.next;
        }

        return -1;
      };

      //Delete an item from the list
      delete = (elm) => {
        return this.removeAt(this.indexOf(elm));
      };    

      //Delete first item from the list
      deleteHead = function(){
        let current = this.head;

        if(current === null){
          return true;
        }

        if(current.next){
          current = current.next;
          this.head = current;       
        }else{
          this.head = null;
        }

        return true;
      }

      //Delete last item from the list
      deleteTail = function(){
        let current = this.head;

        if(current === null){
          return true;
        }

        while(current.next){
          if(!current.next.next){
            current.next = null;
          }else{
            current = current.next;
          }
        }

        return true;
      }

      //Find the item in the list
      isPresent = (elm) => {
        return this.indexOf(elm) !== -1;
      };


      //Check if list is empty
      isEmpty = function(){
        return this.length === 0;
      };

      //Get the size of the list
      size = function(){
        return this.length;
      }

      //Get the head of the list
      getHead = function(){
        return this.head;
      }
  }
})();

Time Complexity

# Access Search Insert Delete
Average Θ(N) Θ(N) Θ(1) Θ(1)
Worst O(N) O(N) O(1) O(1)

Space Complexity

# space
Worst O(N)