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
getwith 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 theunshiftmethod with the val parameter passed in
step 3: if the index is equal to the size property return thepushmethod 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 theindex -1position
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 theshiftshift method.
step 3: if the index is equal to the size property minus
1 return thepopmethod.
step 4: Create a variable prevNode and set it to the results ofgetmethod withindex-1.
step 5: Get the node at theindex -1position,
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:
- Reversing the doubly linked list is very easy.
- It can allocate or reallocate memory easily during its execution.
- As with a singly linked list, it is the easiest data structure to implement.
- The traversal of this doubly linked list is bidirectional which is not possible in a singly linked list.
- 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:
- It uses extra memory when compared to the array and singly linked list.
- 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)