DEV Community

Edwin
Edwin

Posted on

Doubly Linked Lists Implementation JavaScript and Python

#linkedlists #doubly #python #javascript

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.

alt SLL

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)
Enter fullscreen mode Exit fullscreen mode

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()
Enter fullscreen mode Exit fullscreen mode

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 }
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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 }
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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; }
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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; }
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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; }
Enter fullscreen mode Exit fullscreen mode

In python:

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

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; }
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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 }
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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("==============")
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)