Doubly Linked Lists Implementation JavaScript and Python

What is Doubly Linked List?

We already know what a linked list is, from the first section definition. A doubly linked list is by definition and function still the same as an SLL(singly linked lists) with the only difference being that a DLL(doubly linked list)has prev property attached to the node hence you can go back either forward or backwards.

For simplicity, I copied the code from the previous section and adjusted it to include the previous property. Also, the steps in each operation will need to be adjusted a little bit. Let's begin:-

Operations we to be Implemented

• push //add node a the end
• pop // remove node at the end
• shift // remove node at the beginning
• unshift // add a node at the beginning
• get // get node at a specific index or according to criteria
• set // change node value attribute
• insert //
• remove
• reverse // reverse the direction of the list

NB: Below I have done a deep dive into each function or method implementation. All the functions or methods are inside the class: Skip to the end to see the full code implementation then comeback and follow-through

Let's begin, ps: I will be doing the implementations in both Javascript and Python.

Push

In the push function, you will always be adding a node at the end of the list. The steps to follow are outlined below.

Step 1 - Create a newNode with given value and newNode → next as NULL.
Step 2 - Check whether list is Empty (head == NULL).
Step 3 - If it is Empty then, set head = newNode.
Step 4 - If it is Not Empty then point the tails next attribute to the newNode
step 5 - set the newNode's prev property to the current tail node
Step 6 - then reset the tail to point to the newNode and increment the size

code implementation in JavaScript:

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

    }
}

class DLL{
    constructor(){
        this.head= null
        this.tail= null
        this.size= 0

    }

    push(val){
        let newNode= new Node(val);
        if(!this.head){
            this.head=newNode
            this.tail= newNode
            this.size++
            return this
        }
        this.tail.next = newNode
        newNode.prev =this.tail
        this.tail = newNode
        this.size++
        return this
    }
}

let list =new DLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)

In python:

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None


class DLL:
    def __init__(self):
        self.head=None
        self.tail= None
        self.size=0

    def traverse_list(self):
        if(self.head is None):
            print("No elements in this list")
            return
        else:
            n = self.head
            while n is not None:
                print(n.val)
                n = n.next


    def push(self,val):
        newNode =  Node(val)

        if(self.head == None):
            self.head = newNode
            self.tail = newNode
            self.size+=1
            return self
        self.tail.next= newNode
        newNode.prev = self.tail
        self.tail = newNode
        self.size+=1
        return self
list = DLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)
list.traverse_list()

Pop

In the pop function, this involves always removing from the end. The steps to follow are as below

step 1 - Handle the edge case if the list is empty return None or undefined
step 2 - Create a temp and set it to the tail node
step 3 - If the size property is equal to 1 set the head and tail properties to null
step 4 - Set the tail attribute equal to the current tails prev attribute. Also, set the tail's next property to null and the temp variable's prev property to null.
step 5 - return the list

Code implementation in Javascript :

pop(){
        if(!this.head) return undefined;
        let temp = this.tail
        if(this.size ===1){
            this.head = null;
            this.tail = null;
        }else{
        this.tail= this.tail.prev;
        this.tail.next= null;
        temp.prev = null
        }
        this.size--;

        return this
    }

In python:

def pop(self):
        if self.head ==None:return
        temp = self.tail
        if self.size == 1:
            self.head = None
            self.tail = None
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None 
        self.size-=1

        return self

Shift

This involves removing the first node in the list.
The steps to follow are below:

step 1: Check if the head exists otherwise return early
step 2: Initiate a variable called temp set it equal to the head property
step 3: If the size property is one the set the head and tail property to null or None
step 4: Otherwise set the head property to be the current heads next property
step 5: Set the current head's prev property to null
step 6: decrement the size by 1
step 6: Return the list

Code implementation in Javascript :

shift(){
       if(!this.head) return undefined
       let temp = this.head
       if(this.size ===1){
           this.head = null
           this.tail =null
       }else
       this.head = this.head.next;
       this.head.prev = null;
       }
       this.size --

       return temp
   }

In python:

def shift(self):
        if self.head == None: return 
        temp = self.head
        if(self.size == 1):
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
        self.size-=1

        return temp

Unshift

From the name unshift you can guess it is the opposite of shift and it involves adding a node a the beginning. Follow the steps below:

step 1: Create a variable newNode and instantiate the Node class will the val passed in.
step 2: If there is no head property set the head property and tail property equal to the newNode
step 3: if there is a head property set the newNodes's next property to the head property, set the head's prev property to the newNode and then set the head property to the newNode
step 4: Increment the size by 1 and return the list

Code implementation in Javascript :

 unshift(val){
       let newNode = new Node(val);
       if(!this.head){
           this.head= newNode;
           this.tail = newNode;
       }else{
           newNode.next = this.head;
           this.head.prev = newNode;
           this.head = newNode;
       }
       this.size++;
       return this;


   }

In python:

def unshift(self,val):
        newNode = Node(val)
        if self.head == None:
            self.head = newNode
            self.tail = newNode
        else:
            newNode.next = self.head
            self.head.prev = newNode
            self.head = newNode
        self.size+=1
        return self

Get

Get method is just is a search criterion for a node it can use an index or value of the node but in this case, I will just use the index. This implementation is optimized to reduce the number of traversals by half. If the index is greater than half the size of the list we assume it is towards the end of the list, it makes more sense to start searching from the tail and vice versa if it is less than half the size. Follow the steps outline below:

step 1: If the index is less than 0 or greater than or equal to the size property return early
step 2: if index > (size/2) then we set the count to the size property minus one, set the current variable to tail node and start a while loop as long as count is not equal to index, setting current to the current's prev node and decrementing count by one each time
step 2: if index <= (size/2) then we set the count variable to zero, set the current variable to head property, and start a while loop as long as the count is not equal to index, setting current to the current's next node and incrementing count by one each time
step 4: when the loop breaks return current node

Code implementation in Javascript :

  get(index){
       if(index<0 || index >= this.size)return undefined;
       if(index>Math.floor(this.size/2)){
       let count=this.size -1;
       let current= this.tail;
       while(count !== index){
           current= current.prev;
           count--
       }
        }else{
        let count =0;
        let current = this.head
        while(count !== index){
           current= current.next;
           count++
       }

        }

       return current;


   }

In python:

def get(self,index):
        if index <0 or index >=self.size:return
        if index > math.floor(self.size/2):      
            current= self.tail
            count = self.size -1
            while count != index:       
                current = current.next
                count-=1
        else:
            current= self.head
            count = 0
            while count != index:   
                current = current.next
                count+=1
        return current

set

This method will use the Get method to find the node we want and set its value attribute to something else. Follow the steps outlined below:

step 1 : Create a node variable set it to the function get with index passed in as a parameter
step 2 : If the node variable is set to a Non-null or Non- None value set the val property of the node to the new val then return true otherwise return false

Code implementation in Javascript :

  set(index, val){
        let node = this.get(index);
        if(node){
            node.val = val;
            return true;
        }
        return false;
   }

In python:

def set(self,index,val):
        node = self.get(index)
        if node :
            node.val = val
            return True
        return False

Insert

This method will insert a node at a specific point, it will also use the Get method as a helper method to determine where to insert the node. Follow the steps below:

Step 1: If the index parameter is less than zero or greater than the size property return early
step 2: if the index parameter is equal to zero, then return the unshift method with the val parameter passed in
step 3: if the index is equal to the size property return the push method with the val parameter passed in
step 4: Create a variable newNode and instantiate the Node class will the value passed in.
step 5: Get the node at the index -1 position
step 6: Create a nextNode's variable and set it equal to the current node's next property
step 7: set the current node's next property to the newNode and the newNodes's prev property to the node variable, set the newNode's next property to the nextNode and the nextNodes's prev property to the newNode
step 8: Increment the size property by 1 and return the list

Code implementation in Javascript :

insert(index, val){
       if(index<0 || index > this.size ) return undefined
       if(index === 0){
           this.unshift(val);
       }else if(index === this.size){
           this.push(val);
       }else{
           let newNode = new Node(val);
           let node  = this.get(index-1);
           let nextNode = node.next;
           node.next = newNode, newNode.prev = node;
           newNode.next = nextNode, nextNode.prev = newNode;
       }

      this.size++;
      return this;

   }

In python:

def insert(self,index, val):
        if index<0 or index> self.size: return
        if index == 0: return self.unshift(val)
        if index == self.size: return self.push(val)
        newNode = Node(val)
        prevNode = self.get(index-1)
        nextNode = prevNode.next
        prevNode.next = newNode 
        newNode.prev= prevNode
        newNode.next = nextNode 
        nextNode.prev = newNode
        self.size+=1
        return self

Remove

This method removes an element from the list.The steps to follow are outlined below:

Step 1: If the index parameter is less than zero or greater than or equal to the size property return early
step 2: if the index parameter is equal to zero, the return the shift shift method.
step 3: if the index is equal to the size property minus
1 return the pop method.
step 4: Create a variable prevNode and set it to the results of get method with index-1.
step 5: Get the node at the index -1 position,
step 6: Create a temp variable and set it equal to the prevNode's next property, create another afterNode and set it to be the temp's variable next property, then set the prevNode's next property to be the afterNode, set the afterNode prev's property to be the prevNode, set hte temp's next and temp's prev property to null
step 7: decrement the size property by 1 and return the list

Code implementation in Javascript :

   remove(index){
       if(index<0 || index >= this.size ) return undefined
       if(index === 0) return this.shift()
       if(index === this.size-1) return this.pop()
        let prevNode = this.get(index-1)
        let temp = prevNode.next
        let afterNode = temp.next
        prevNode.next = afterNode
        afterNode.prev = prevNode
        temp.next = null
        temp.prev = null
        this.size--
        return this

   }

In python:

def remove(self,index):
         if index<0 or index>= self.size: return
         if index == 0:
             return self.shift()
         if index == self.size-1:
            return self.pop()
         prevNode = self.get(index-1)
         temp = prevNode.next
         afterNode = temp.next
         prevNode.next = afterNode
         afterNode.prev = prevNode
         temp.next = None
         temp.prev = None
         self.size-=1
         return self

Final Code solution for JavaScript :

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

    }
}

class DLL{
    constructor(){
        this.head= null
        this.tail= null
        this.size= 0

    }

    push(val){
        let newNode= new Node(val);
        if(!this.head){
            this.head=newNode
            this.tail= newNode
            this.size++
            return this
        }
        this.tail.next = newNode
        newNode.prev =this.tail
        this.tail = newNode
        this.size++
        return this
    }
    pop(){
        if(!this.head) return undefined;
        let temp = this.tail
        if(this.size ===1){
            this.head = null;
            this.tail = null;
        }else{
        this.tail=this.tail.prev;
        this.tail.next = null;
        temp.prev= null;
        }
        this.size--;

        return this;
    }

   //shift
   shift(){
       if(!this.head) return undefined
       let temp = this.head;
       if(this.size ===1){
           this.head = null
           this.tail =null;
       }else{
       this.head = this.head.next;
       this.head.prev = null
       }
       this.size --;

       return temp
   }
   //unshift
   unshift(val){
       let newNode = new Node(val);
       if(!this.head){
           this.head= newNode;
           this.tail = newNode;
       }else{
           newNode.next = this.head;
           this.head.prev = newNode;
           this.head = newNode;
       }
       this.size++;
       return this;


   }
   //get
   get(index){
       if(index<0 || index >= this.size)return undefined;
       let current;
       if(index >Math.floor(this.size/2)){
           let count=this.size-1;
            current= this.tail;
          while(count !== index){
             current= current.prev;
             count--
       }

       }else{
           let count=0;
            current= this.head;
           while(count !== index){
              current= current.next;
              count++
       }
       }
       return current;
   }
   //set
   set(index, val){
        let node = this.get(index);
        if(node){
            node.val = val;
            return true;
        }
        return false;
   }
   //insert
   insert(index, val){
       if(index<0 || index > this.size ) return undefined
       if(index === 0){
           this.unshift(val);
       }else if(index === this.size){
           this.push(val);
       }else{
           let newNode = new Node(val);
           let node  = this.get(index -1);
           let nextNode = node.next;
               node.next = newNode, newNode.prev = node;
               newNode.next = nextNode, nextNode.prev = newNode
       }

      this.size++;
      return this;

   }
   //remove
   remove(index){
       if(index<0 || index >= this.size ) return undefined
       if(index === 0) return this.shift()
       if(index === this.size-1) return this.pop()
        let prevNode = this.get(index-1)
        let temp = prevNode.next
        let afterNode = temp.next
        prevNode.next = afterNode
        afterNode.prev = prevNode
        temp.next = null
        temp.prev = null

        this.size--
        return temp

   }
   //reverse

   //print
   print(){
       let current= this.head
       let arr = []
       while(current){
           arr.push(current.val)
           current = current.next
       }
       return arr
   }
}
let list =new DLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)

for Python:

import math
class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None


class DLL:
    def __init__(self):
        self.head=None
        self.tail= None
        self.size=0

    def traverse_list(self):
        if(self.head is None):

            print("No elements in this list")
            return
        else:
            n = self.head
            while n is not None:
                print(n.val)
                n = n.next


    def push(self,val):
        newNode =  Node(val)

        if(self.head == None):
            self.head = newNode
            self.tail = newNode
            self.size+=1
            return self
        self.tail.next= newNode
        newNode.prev = self.tail
        self.tail = newNode
        self.size+=1
        return self

    def pop(self):

        if self.head ==None:return
        temp = self.tail
        if self.size == 1:
            self.head = None
            self.tail = None
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None 
        self.size-=1

        return self

    def shift(self):
            if self.head == None: return 
            temp = self.head
            if(self.size == 1):
                self.head = None
                self.tail = None
            else:
                self.head = self.head.next
                self.head.prev = None
            self.size-=1

            return temp

    def unshift(self,val):
        newNode = Node(val)
        if self.head == None:
            self.head = newNode
            self.tail = newNode
        else:
            newNode.next = self.head
            self.head.prev = newNode
            self.head = newNode
        self.size+=1
        return self

    def get(self,index):
        if index <0 or index >=self.size:return
        if index > math.floor(self.size/2):      
            current= self.tail
            count = self.size -1
            while count != index:       
                current = current.next
                count-=1
        else:
            current= self.head
            count = 0
            while count != index:   
                current = current.next
                count+=1
        return current

    def set(self,index,val):
        node = self.get(index)
        if node :
            node.val = val
            return True
        return False

    def insert(self,index, val):
        if index<0 or index> self.size: return
        if index == 0: return self.unshift(val)
        if index == self.size: return self.push(val)
        newNode = Node(val)
        prevNode = self.get(index-1)
        nextNode = prevNode.next
        prevNode.next = newNode 
        newNode.prev= prevNode
        newNode.next = nextNode 
        nextNode.prev = newNode
        self.size+=1
        return self

    def remove(self,index):
         if index<0 or index>= self.size: return
         if index == 0:
             return self.shift()
         if index == self.size-1:
            return self.pop()
         prevNode = self.get(index-1)
         temp = prevNode.next
         afterNode = temp.next
         prevNode.next = afterNode
         afterNode.prev = prevNode
         temp.next = None
         temp.prev = None
         self.size-=1
         return self

list = DLL()
list.push(20)
list.push(21)
list.push(22)
list.push(23)
list.traverse_list()   

print("==============")
list.remove(2)
print("==============")
print("==============")
list.traverse_list()   

print("==============")

As you can observe the final solution bears some similarity to the SLL solution with some small differences.

Advantages Of DLL:

1. Reversing the doubly linked list is very easy.
2. It can allocate or reallocate memory easily during its execution.
3. As with a singly linked list, it is the easiest data structure to implement.
4. The traversal of this doubly linked list is bidirectional which is not possible in a singly linked list.
5. Deletion of nodes is easy as compared to a Singly Linked List. A singly linked list deletion requires a pointer to the node and previous node to be deleted but in the doubly linked list, it only required the pointer which is to be deleted.

Disadvantages Of DLL:

1. It uses extra memory when compared to the array and singly linked list.
2. Since elements in memory are stored randomly, therefore the elements are accessed sequentially no direct access is allowed.

Conclusion

You can look up this article for more information on doubly linked lists and their uses. Next in this series, We will take a look at implementing stack and Queues using Linked lists.