Doubly linked list implementation in javascript

We will see what is doubly linked list and why is this data structure is needed and also implement an object-based doubly linked list in javascript.

Why do we need doubly linked list?

If you do not already know what is single linked list then I would recommend to understand it first before learning this.

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.

However, in the single linked list we can only move forward to the next element but cannot go back.

But in the doubly linked list, we maintain two pointers
1. For the next element.
2. For the previous element.

This way we will be able to iterate backward any time we want. Check out the following image to get a good reference.

Doubly linked list in Javascript

Now I am sure you have a good idea about why we need doubly linked list, so let us start implementing an object-based doubly linked list in javascript.

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 to iterate in forward direction.
  • getTail(): Returns the whole list to itreate in backward direction.

Implementing a doubly linked list in javascript

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

function doubleLinkedList() {
  //Node
  let Node = function(element) {
    this.element = element;
    this.next = null;
    this.prev = null;
  }

  let length = 0;
  let head = null;
  let tail = null;

  //Other methods go here
}

Adding an item in the doubly linked list

If the head is empty then assign the current Node to the head else add the Node as the next element and mark the exisiting as previous element.

//Append a new element
this.append = function(element) {
    let node = new Node(element),
          current = head,
          previous;
    
    if(!head){
          head = node;
          tail = node;
     }else{
       node.prev = tail;
       tail.next = node;
       tail = node;
     }
    
    length++;
  }

Insert an element at the given position in doubly linked list

There are three different cases while inserting an element in the doubly linked list.

Insert at the beginning

If the current element is to be added at the start then just make all the existing elements as the next element of the current element.

Insert at head in double linked list


Insert in the middle

It is a little complicated step.
If we are going to insert an element in the middle then we will have to make the previous element to point to the current element and current element to point to the next element of the current element.
Insert at middle in double linked list


Insert at the end

To add the element at the last then we will just have to make sure that last element points to the current element and the current points to null.
Insert at tail in double linked list

//Add element at any position
  this.insert = function(position, element) {
    
    //Check of out-of-bound values
    if(position >= 0 && position <= length){
      let node = new Node(element),
          current = head,
          previous,
          index = 0;
      
      if(position === 0){
        if(!head){
          head = node;
          tail = node;
        }else{
          node.next = current;
          current.prev = node;
          head = node;
        }
      }else if(position === length){
        current = tail;
        current.next = node;
        node.prev = current;
        tail = node;
      }else{
        while(index++ < position){
          previous = current;
          current = current.next;
        }
        
        node.next = current;
        previous.next = node;
        
        //New
        current.prev = node;
        node.prev = previous; 
      }
      
      length++;
      return true;
    }else{
      return false;
    }
  }

Remove an element from the given position in doubly linked list

There are three different cases while removing an element from the doubly linked list.

Remove the first element

If the current element is to removed then just move the head to the very next element.
Remove head in double linked list


Remove the middle element

This is a little complicated process so we need to implement this carefully.
If we are going to remove an element from the middle then we will have to make the previous element to point to the next element and next element to point to the previous element of the current element.
Remove from middle in double linked list


Remove the last element

To remove the last element will just have to make sure previous element point to the null.
Remove tail in double linked list

//Remove element at any position
  this.removeAt = function(position){
    //look for out-of-bounds value
    if(position > -1 && position < length){
      let current = head, previous, index = 0;
      
      //Removing first item
      if(position === 0){
        head = current.next;
        
        //if there is only one item, update tail //NEW
        if(length === 1){
          tail = null;
        }else{
          head.prev = null;
        }
      }else if(position === length - 1){
        current = tail;
        tail = current.prev;
        tail.next = null;
      }else{
        while(index++ < position){
          previous = current;
          current = current.next;
        }
        
        //link previous with current's next - skip it
        previous.next = current.next; 
        current.next.prev = previous;
      }
      
      length--;
      return current.element;
    }else{
      return null;
    }
  }

Getting index of the given element

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 doubly linked list

We can store any type of data in a doubly-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 an element from the doubly linked list

To delete an element from the list we will find the index of the element and remove it.

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

Delete the head from the doubly linked list

To remove the head from the doubly linked list we will just have to remove the first element.

//Delete the first item from the list
  this.deleteHead = function(){
    this.removeAt(0);
  }

Delete the tail from the doubly linked list

To remove the tail from the doubly linked list we will just have to remove the last element.

//Delete the last item from the list
  this.deleteTail = function(){
    this.removeAt(length-1);
  }

Return the doubly linked list as 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 doubly linked list as an array

We will add all the elements of the list to an 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 doubly linked list is empty

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

Get the size of doubly linked 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;
}

Get the tail of the list

//Get the tail of the list
this.getTail = function(){
  return tail;
}

Complete code of the doubly linked list in javascript.

function doubleLinkedList() {
  let Node = function(element) {
    this.element = element;
    this.next = null;
    this.prev = null;
  }
  
  let length = 0;
  let head = null;
  let tail = null;
  
  //Add new element
  this.append = function(element) {
    let node = new Node(element),
          current = head,
          previous;
    
    if(!head){
          head = node;
          tail = node;
     }else{
       node.prev = tail;
       tail.next = node;
       tail = node;
     }
    
    length++;
  }
  
  
  //Add element 
  this.insert = function(position, element) {
    
    //Check of out-of-bound values
    if(position >= 0 && position <= length){
      let node = new Node(element),
          current = head,
          previous,
          index = 0;
      
      if(position === 0){
        if(!head){
          head = node;
          tail = node;
        }else{
          node.next = current;
          current.prev = node;
          head = node;
        }
      }else if(position === length){
        current = tail;
        current.next = node;
        node.prev = current;
        tail = node;
      }else{
        while(index++ < position){
          previous = current;
          current = current.next;
        }
        
        node.next = current;
        previous.next = node;
        
        //New
        current.prev = node;
        node.prev = previous; 
      }
      
      length++;
      return true;
    }else{
      return false;
    }
  }
  
  //Remove element at any position
  this.removeAt = function(position){
    //look for out-of-bounds value
    if(position > -1 && position < length){
      let current = head, previous, index = 0;
      
      //Removing first item
      if(position === 0){
        head = current.next;
        
        //if there is only one item, update tail //NEW
        if(length === 1){
          tail = null;
        }else{
          head.prev = null;
        }
      }else if(position === length - 1){
        current = tail;
        tail = current.prev;
        tail.next = null;
      }else{
        while(index++ < position){
          previous = current;
          current = current.next;
        }
        
        //link previous with current's next - skip it
        previous.next = current.next; 
        current.next.prev = previous;
      }
      
      length--;
      return current.element;
    }else{
      return null;
    }
  }
  
  //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;
  };
  
  //Find the item in the list
  this.isPresent = (elm) => {
    return this.indexOf(elm) !== -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(){
    this.removeAt(0);
  }
  
  //Delete last item from the list
  this.deleteTail = function(){
    this.removeAt(length-1);
  }
  
  //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;
  };
  
  //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
  this.getHead = function() {
    return head;
  }
  
  //Get the tail
  this.getTail = function() {
    return tail;
  }
} 
Input:
let dll = new doubleLinkedList();
dll.append('prashant');
dll.append('surag');
dll.append('sachin');
dll.insert(1, 'omkar');
dll.deleteHead();
dll.deleteTail();
dll.deleteHead();
console.log(dll.toArray());

Output:
["surag"]

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

let doubleLinkedList = (function(){
  return function doubleLinkedList() {
      let Node = function(element) {
        this.element = element;
        this.next = null;
        this.prev = null;
      }

      let length = 0;
      let head = null;
      let tail = null;

      //Add new element
      this.append = function(element) {
        let node = new Node(element),
              current = head,
              previous;

        if(!head){
              head = node;
              tail = node;
         }else{
           node.prev = tail;
           tail.next = node;
           tail = node;
         }

        length++;
      }


      //Add element 
      this.insert = function(position, element) {

        //Check of out-of-bound values
        if(position >= 0 && position <= length){
          let node = new Node(element),
              current = head,
              previous,
              index = 0;

          if(position === 0){
            if(!head){
              head = node;
              tail = node;
            }else{
              node.next = current;
              current.prev = node;
              head = node;
            }
          }else if(position === length){
            current = tail;
            current.next = node;
            node.prev = current;
            tail = node;
          }else{
            while(index++ < position){
              previous = current;
              current = current.next;
            }

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

            //New
            current.prev = node;
            node.prev = previous; 
          }

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

      //Remove element at any position
      this.removeAt = function(position){
        //look for out-of-bounds value
        if(position > -1 && position < length){
          let current = head, previous, index = 0;

          //Removing first item
          if(position === 0){
            head = current.next;

            //if there is only one item, update tail //NEW
            if(length === 1){
              tail = null;
            }else{
              head.prev = null;
            }
          }else if(position === length - 1){
            current = tail;
            tail = current.prev;
            tail.next = null;
          }else{
            while(index++ < position){
              previous = current;
              current = current.next;
            }

            //link previous with current's next - skip it
            previous.next = current.next; 
            current.next.prev = previous;
          }

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

      //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;
      };

      //Find the item in the list
      this.isPresent = (elm) => {
        return this.indexOf(elm) !== -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(){
        this.removeAt(0);
      }

      //Delete last item from the list
      this.deleteTail = function(){
        this.removeAt(length-1);
      }

      //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;
      };

      //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
      this.getHead = function() {
        return head;
      }

      //Get the tail
      this.getTail = function() {
        return tail;
      }
    } 
}());
Input:
let dll = new doubleLinkedList();
dll.append('prashant');
dll.append('surag');
dll.append('sachin');
dll.insert(1, 'omkar');
dll.deleteHead();
dll.deleteTail();
dll.deleteHead();
console.log(dll.toArray());

Output:
["surag"]

Class based implementation of doubly linked list in javascript

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

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

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

    //Add new element
    append = function(element) {
      let node = new Node(element),
          current = this.head,
          previous;

      if(!this.head){
        this.head = node;
        this.tail = node;
      }else{
        node.prev = this.tail;
        this.tail.next = node;
        this.tail = node;
      }

      this.length++;
    }


  //Add element 
  insert = function(position, element) {

    //Check of out-of-bound values
    if(position >= 0 && position <= this.length){
      let node = new Node(element),
          current = this.head,
          previous,
          index = 0;

      if(position === 0){
        if(!this.head){
          this.head = node;
          this.tail = node;
        }else{
          node.next = current;
          current.prev = node;
          this.head = node;
        }
      }else if(position === this.length){
        current = this.tail;
        current.next = node;
        node.prev = current;
        this.tail = node;
      }else{
        while(index++ < position){
          previous = current;
          current = current.next;
        }

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

        //New
        current.prev = node;
        node.prev = previous; 
      }

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

  //Remove element at any position
  removeAt = function(position){
    //look for out-of-bounds value
    if(position > -1 && position < this.length){
      let current = this.head, previous, index = 0;

      //Removing first item
      if(position === 0){
        this.head = current.next;

        //if there is only one item, update tail //NEW
        if(length === 1){
          this.tail = null;
        }else{
          this.head.prev = null;
        }
      }else if(position === this.length - 1){
        current = this.tail;
        this.tail = current.prev;
        this.tail.next = null;
      }else{
        while(index++ < position){
          previous = current;
          current = current.next;
        }

        //link previous with current's next - skip it
        previous.next = current.next; 
        current.next.prev = previous;
      }

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

  //Get the indexOf item 
  indexOf = function(elm){
    let current = this.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;
  };

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

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

  //Delete first item from the list
  deleteHead = function(){
    this.removeAt(0);
  }

  //Delete last item from the list
  deleteTail = function(){
    this.removeAt(this.length-1);
  }

  //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;
  };

  //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
  getHead = function() {
    return this.head;
  }

  //Get the tail
  getTail = function() {
    return this.tail;
  }
}

Making this class private with closure and IIFE

let doubleLinkedList = (function(){
  //Node
  class Node{
    constructor(elm, next = null, prev=null){
      this.element = elm;
      this.next = next;
      this.prev = prev;
    }
  }
 
return class doubleLinkedList{
      constructor(){
        this.length = 0;
        this.head = null;
        this.tail = null;
      }

      //Add new element
      append = function(element) {
        let node = new Node(element),
            current = this.head,
            previous;

        if(!this.head){
          this.head = node;
          this.tail = node;
        }else{
          node.prev = this.tail;
          this.tail.next = node;
          this.tail = node;
        }

        this.length++;
      }


    //Add element 
    insert = function(position, element) {

      //Check of out-of-bound values
      if(position >= 0 && position <= this.length){
        let node = new Node(element),
            current = this.head,
            previous,
            index = 0;

        if(position === 0){
          if(!this.head){
            this.head = node;
            this.tail = node;
          }else{
            node.next = current;
            current.prev = node;
            this.head = node;
          }
        }else if(position === this.length){
          current = this.tail;
          current.next = node;
          node.prev = current;
          this.tail = node;
        }else{
          while(index++ < position){
            previous = current;
            current = current.next;
          }

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

          //New
          current.prev = node;
          node.prev = previous; 
        }

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

    //Remove element at any position
    removeAt = function(position){
      //look for out-of-bounds value
      if(position > -1 && position < this.length){
        let current = this.head, previous, index = 0;

        //Removing first item
        if(position === 0){
          this.head = current.next;

          //if there is only one item, update tail //NEW
          if(length === 1){
            this.tail = null;
          }else{
            this.head.prev = null;
          }
        }else if(position === this.length - 1){
          current = this.tail;
          this.tail = current.prev;
          this.tail.next = null;
        }else{
          while(index++ < position){
            previous = current;
            current = current.next;
          }

          //link previous with current's next - skip it
          previous.next = current.next; 
          current.next.prev = previous;
        }

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

    //Get the indexOf item 
    indexOf = function(elm){
      let current = this.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;
    };

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

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

    //Delete first item from the list
    deleteHead = function(){
      this.removeAt(0);
    }

    //Delete last item from the list
    deleteTail = function(){
      this.removeAt(this.length-1);
    }

    //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;
    };

    //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
    getHead = function() {
      return this.head;
    }

    //Get the tail
    getTail = function() {
      return this.tail;
    }
  } 
}());

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)