Circular Doubly linked list in javascript

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

What is circular doubly linked list?

A circular doubly linked list is a variation of linked list in which there is no end to the list. The last element of the list will point to the first element instead of pointing to the null and the first element will point to the last element. All the nodes are connected to form a circle.

Circular doubly linked list

Both single linked list and doubly linked list can be used to create a circular linked list.

We have already implemented a circular single linked list and have listed its advantages and disadvantages.

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


List of operations performed on circular doubly 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.
  • getElementAt(position): Returns the node 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.
  • 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 iterate in reverse direction.

Implementing a circular double linked list in javascript

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

function circularLinkedList() {
  //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
}

Getting element at a given position

Returns the node at the given index in the list. We will use this function as a helper function to get the nodes at the specific index to create a circular double linked list.

//Get element at specific index
  this.getElementAt = function(index) {
    if(index >= 0 && index <= length){
      let node = head;
      for(let i = 0; i < index && node != null; i++){
        node = node.next;
      }
      return node;
    }
    return undefined;
  }

Adding an item in the circular double linked list

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

After each insertion mark the first Node as head and last Node as the tail. And then make them point to each other.

//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;
    }
    
    //Mark head's prev element as last element
    head.prev = tail;
    
    //Mark tail's next element as first element
    tail.next = head;
    length++;
  }

Inserting element at given position in circular double linked list

There are three different cases while inserting an element in the circular 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 and make the last element to point the new node.
Adding a node at head in circular doubly linked list


Adding new element in the middle

It is a little more complex, we need to make the element at the current index to point to the current element and current element to point to the next element and mark it as previous of next element.
Adding a node at middle in circular doubly linked list


Inserting a new element at the tail.

If the node is to be added to the end then make the last element point to the new element and new element point to the first element and first element to point the last element.
Adding a node at tail in circular doubly 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; 
      }
      
      //Mark head's prev element as last element
      head.prev = tail;
    
      //Mark tail's next element as first element
      tail.next = head;
      
      length++;
      return true;
    }else{
      return false;
    }
  }

Removing element at given position in circular linked list

This step also has three different cases which needs to be handled.

Remove from the head

If the element is to be removed from the start then just make head point to the next element of the current element and make the last element to point the new head.
Remove head in circular doubly linked list


Deleting a middle node from the doubly linked list

It is a little more complex process, we need to make the previous element of the element at the current index to point to the next element of the current element.
Remove from middle in circular doubly linked list


Removing an element from the tail

If the node is to be removed from the tail then we need to make the second last node to point to the head.
Remove tail in circular doubly linked list

//Remove at any position
  this.removeAt = function (index) {
    if(index >= 0 && index < length){
      let current = head;
      
      //Remove from head
      if(index === 0){
        if(length === 1){
          head = undefined;
        }else{
          const removed = head;
          current = this.getElementAt(length - 1);
          head = head.next;
          current.next = head;
          current = removed;
        }
      }else{
        //Remove at given index (middle or end)
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      
      if(head){
        //Mark head's prev element as last element
        head.prev = tail;
    
        //Mark tail's next element as first element
        tail.next = head;
      }
      
      length--;
      return current.element;
    }
    return undefined;
  }

Get the index of the element in the circular linked list

We will be returning the zero-based index for linked list elements just like arrays, If the 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 circular double 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;
  };

Get the head of the circular list

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

Get the tail of the circular list

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

Delete an element from the circular 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 head from the circular linked list

To delete head from the list just remove the element at index 0.

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

Delete tail from the circular linked list

To delete tail from the list just remove the element at index size - 1.

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

Get the circular list as a string

It is complex to print the list as a string because we have to be careful while iterating the list that we don't end up an infinite loop.

So will keep track of the elements and break the loop once elements are repeated.

//Print item of the string
  this.toString = function(){
    let current = head,
    string = '';
    const temp = head.element;
    
    while(current){
      if(temp === current.next.element){
        string += current.element + (current.next ? '\n' : '');
        break;
      }
      
      string += current.element + (current.next ? '\n' : '');
      current = current.next;
    }

    return string;
  };

Get the circular linked list as an array

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

    while(current){
      //Break if first element detected
      if(temp === current.next.element){
        arr.push(current.element);
        break;
      }
      
      arr.push(current.element);
      current = current.next;
    }

    return arr;
  };

Check if circular doubly linked 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;
  }

Complete code of the circular linked list in javascript.

function circularLinkedList() {
  //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 
  
  //Get element at specific index
  this.getElementAt = function(index) {
    if(index >= 0 && index <= length){
      let node = head;
      for(let i = 0; i < index && node != null; i++){
        node = node.next;
      }
      return node;
    }
    return undefined;
  }
  
  //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;
    }
    
    //Mark head's prev element as last element
    head.prev = tail;
    
    //Mark tail's next element as first element
    tail.next = head;
    length++;
  }
  
  //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; 
      }
      
      //Mark head's prev element as last element
      head.prev = tail;
    
      //Mark tail's next element as first element
      tail.next = head;
      
      length++;
      return true;
    }else{
      return false;
    }
  }
  
  //Remove at any position
  this.removeAt = function (index) {
    if(index >= 0 && index < length){
      let current = head;
      
      //Remove from head
      if(index === 0){
        if(length === 1){
          head = undefined;
        }else{
          const removed = head;
          current = this.getElementAt(length - 1);
          head = head.next;
          current.next = head;
          current = removed;
        }
      }else{
        //Remove at given index (middle or end)
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      
      if(head){
        //Mark head's prev element as last element
        head.prev = tail;
    
        //Mark tail's next element as first element
        tail.next = head;
      }
      
      length--;
      return current.element;
    }
    return undefined;
  }
  
  //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;
  };
  
  //Get the head
  this.getHead = function(){
    return head;
  }
  
  //Get the tail
  this.getTail = function(){
    return tail;
  }
  
  //Delete an item from the list
  this.delete = (elm) => {
     return this.removeAt(this.indexOf(elm));
  }; 
  
  //Delete the first item from the list
  this.deleteHead = function(){
    this.removeAt(0);
  }
  
  //Print item of the string
  this.toString = function(){
    let current = head,
    string = '';
    const temp = head.element;
    
    while(current){
      if(temp === current.next.element){
        string += current.element + (current.next ? '\n' : '');
        break;
      }
      
      string += current.element + (current.next ? '\n' : '');
      current = current.next;
    }

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

    while(current){
      //Break if first element detected
      if(temp === current.next.element){
        arr.push(current.element);
        break;
      }
      
      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;
  }
}
Input:
let cLL = new circularLinkedList();
cLL.append(10);
cLL.append(20);
cLL.append(30);
cLL.insert(3, 50);
cLL.removeAt(0);
console.log(cLL.toArray());

Output:
[20, 30, 50]

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

let circularLinkedList = (function(){
  return function circularLinkedList() {
    //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 

    //Get element at specific index
    this.getElementAt = function(index) {
      if(index >= 0 && index <= length){
        let node = head;
        for(let i = 0; i < index && node != null; i++){
          node = node.next;
        }
        return node;
      }
      return undefined;
    }

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

      //Mark head's prev element as last element
      head.prev = tail;

      //Mark tail's next element as first element
      tail.next = head;
      length++;
    }

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

        //Mark head's prev element as last element
        head.prev = tail;

        //Mark tail's next element as first element
        tail.next = head;

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

    //Remove at any position
    this.removeAt = function (index) {
      if(index >= 0 && index < length){
        let current = head;

        //Remove from head
        if(index === 0){
          if(length === 1){
            head = undefined;
          }else{
            const removed = head;
            current = this.getElementAt(length - 1);
            head = head.next;
            current.next = head;
            current = removed;
          }
        }else{
          //Remove at given index (middle or end)
          const previous = this.getElementAt(index - 1);
          current = previous.next;
          previous.next = current.next;
        }

        if(head){
          //Mark head's prev element as last element
          head.prev = tail;

          //Mark tail's next element as first element
          tail.next = head;
        }

        length--;
        return current.element;
      }
      return undefined;
    }

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

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

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

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

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

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

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

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

      return string;
    };

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

      while(current){
        //Break if first element detected
        if(temp === current.next.element){
          arr.push(current.element);
          break;
        }

        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;
    }
  }
}());

ES6 class based implementation of cicular doubly linked list in javascript.

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

class circularLinkedList{
    constructor(){
      this.length = 0;
      this.head = null;
      this.tail = null;
    }
    
    //Get element at specific index
    getElementAt = function(index) {
      if(index >= 0 && index <= this.length){
        let node = this.head;
        for(let i = 0; i < index && node != null; i++){
          node = node.next;
        }
        return node;
      }
      return undefined;
    }

    //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;
      }
      
      //Mark head's prev element as last element
      this.head.prev = this.tail;

      //Mark tail's next element as first element
      this.tail.next = this.head;
  
      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; 
      }
      
      //Mark head's prev element as last element
      this.head.prev = this.tail;

      //Mark tail's next element as first element
      this.tail.next = this.head;

      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;
      }
      
      if(this.head){
        //Mark head's prev element as last element
        this.head.prev = this.tail;

        //Mark tail's next element as first element
        this.tail.next = this.head;
      }

      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 = '';

    //Keep track of the head
    const temp = this.head.element;
    
    while(current){
      //If head is the next element then break
      if(temp === current.next.element){
        string += current.element + (current.next ? '\n' : '');
        break;
      }
      
      string += current.element + (current.next ? '\n' : '');
      current = current.next;
    }

    return string;
  };

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

    //Keep track of head
    const temp = this.head.element

    while(current){
      //Break if first element detected
      if(temp === current.next.element){
        arr.push(current.element);
        break;
      }
      
      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 circularLinkedList = (function(){
  //Node
  class Node{
    constructor(elm, next = null, prev=null){
      this.element = elm;
      this.next = next;
      this.prev = prev;
    }
  }

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

      //Get element at specific index
      getElementAt = function(index) {
        if(index >= 0 && index <= this.length){
          let node = this.head;
          for(let i = 0; i < index && node != null; i++){
            node = node.next;
          }
          return node;
        }
        return undefined;
      }

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

        //Mark head's prev element as last element
        this.head.prev = this.tail;

        //Mark tail's next element as first element
        this.tail.next = this.head;

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

        //Mark head's prev element as last element
        this.head.prev = this.tail;

        //Mark tail's next element as first element
        this.tail.next = this.head;

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

        if(this.head){
          //Mark head's prev element as last element
          this.head.prev = this.tail;

          //Mark tail's next element as first element
          this.tail.next = this.head;
        }

        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 = '';

      //Keep track of the head
      const temp = this.head.element;

      while(current){
        //If head is the next element then break
        if(temp === current.next.element){
          string += current.element + (current.next ? '\n' : '');
          break;
        }

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

      return string;
    };

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

      //Keep track of head
      const temp = this.head.element

      while(current){
        //Break if first element detected
        if(temp === current.next.element){
          arr.push(current.element);
          break;
        }

        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)