Deque or doubly ended queues are linear data structures with which we can perform last in first out (LIFO) operations as well as first in first out (FIFO) operations. Deques have many applications in real life such as implementing undo operation in softwares and in storing the browsing history in web browsers. In this article, we will implement deque in python using linked lists.
How to implement deque using a linked list in python?
Linked list is a linear data structure data structure which consists of nodes which contain data. Each node of a linked list points to another node in the linked list. To implement deque in python using linked list, we will have to perform insertion and deletion operation on both ends of the linked list. Also, we will have to keep a record of the length of the deque.
To create a linked list, we will define a node which will have a data field and a next field. The data field contains the actual data and the next field has a reference to the next node in the linked list. A Node class can be defined in python as follows.
class Node:
def __init__(self,data):
self.data=data
self.next=None
To implement deque using linked list,We will define a class Deque which contains a reference named front to the first element of the linked list and a dequeSize field to keep the size of deque as follows.
class Deque:
def __init__(self):
self.front=None
self.dequeSize=0
Insert an element in deque in python
We can insert it at the front as well as rear of the deque. To insert an element in the deque at front, we will add the element at the start of the linked list. As the start of the linked list is referenced by front, we will add the element before the node currently being referenced by the front and then we will increment the dequeSize by one. This can be implemented as follows.
def insertAtFront(self,data):
temp=Node(data)
if self.front==None:
self.front=temp
self.dequeSize=self.dequeSize+1
else:
temp.next=self.front
self.front=temp
self.dequeSize=self.dequeSize+1
To insert an element at the rear of the deque, we will have to add the element at the end of the linked list.After that we will increment the dequeSize as follows.
def insertAtRear(self,data):
temp=Node(data)
if self.front==None:
self.front=temp
self.dequeSize=self.dequeSize+1
else:
curr=self.front
while curr.next!=None:
curr=curr.next
curr.next=temp
self.dequeSize=self.dequeSize+1
Delete an element from the deque in python
We can delete an element from the front as well as rear of the deque.Before deleting the element, we will check if the deque is empty. If the deque is empty i.e. front points to None, we will raise an exception using python try except with a message that the deque is empty.
To delete an element from the front of the deque, we will have to delete the element from the start of the linked list which is being referenced by front. After deleting the front element, we will decrement the dequeSize by one. This can be implemented as follows.
def delFromFront(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
temp=self.front
self.front=self.front.next
self.dequeSize=self.dequeSize-1
del temp
except Exception as e:
print(str(e))
To delete the element from the rear of the deque, we will delete the last element of the linked list. After deleting the last element, we will decrement the dequeSize by one. This can be implemented as follows.
def deleteFromRear(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
curr=self.front
prev=None
while curr.next!=None:
prev=curr
curr=curr.next
prev.next=curr.next
self.dequeSize=self.dequeSize-1
del curr
except Exception as e:
print(str(e))
Check the size of the deque
To check the size of the deque, we simply have to check the value in the dequeSize field of the deque.This can be done as follows.
def dequeLength(self):
return self.dequeSize
Check if the deque is empty
To check if the deque is empty, we will have to check if the dequeSize is zero. We can implement isEmpty() method which returns True if the dequeSize is zero and otherwise returns False as follows.
def isEmpty(self):
if self.dequeSize==0:
return True
return False
Check front and rear elements in a deque
To check the front element of the deque, we will define a method getfront() which returns the first element of the linked list as follows.
def getfront(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
return self.front.data
except Exception as e:
print(str(e))
To check the rear element of the deque, we will define a method getrear() which returns the last element of the linked list as follows.
def getrear(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
curr=self.front
while curr.next!=None:
curr=curr.next
return curr.data
except Exception as e:
print(str(e))
The complete working code implement deque in python is follows.
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed May 5 23:41:28 2021
@author: aditya1117
"""
class Node:
def __init__(self,data):
self.data=data
self.next=None
class Deque:
def __init__(self):
self.front=None
self.dequeSize=0
def isEmpty(self):
if self.dequeSize==0:
return True
return False
def dequeLength(self):
return self.dequeSize
def insertAtFront(self,data):
temp=Node(data)
if self.front==None:
self.front=temp
self.dequeSize=self.dequeSize+1
else:
temp.next=self.front
self.front=temp
self.dequeSize=self.dequeSize+1
def insertAtRear(self,data):
temp=Node(data)
if self.front==None:
self.front=temp
self.dequeSize=self.dequeSize+1
else:
curr=self.front
while curr.next!=None:
curr=curr.next
curr.next=temp
self.dequeSize=self.dequeSize+1
def delFromFront(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
temp=self.front
self.front=self.front.next
self.dequeSize=self.dequeSize-1
del temp
except Exception as e:
print(str(e))
def deleteFromRear(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
curr=self.front
prev=None
while curr.next!=None:
prev=curr
curr=curr.next
prev.next=curr.next
self.dequeSize=self.dequeSize-1
del curr
except Exception as e:
print(str(e))
def getfront(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
return self.front.data
except Exception as e:
print(str(e))
def getrear(self):
try:
if self.dequeSize==0:
raise Exception("Deque is Empty")
else:
curr=self.front
while curr.next!=None:
curr=curr.next
return curr.data
except Exception as e:
print(str(e))
Read More: Java Program to Decrement Each Element of Array by 1 and Print the Decremented Array