Implement Deque in Python

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 the 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 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))

Conclusion

In this article, we have studied the concept behind deque and have implemented it using linked list in python. To gain more insight into it and understand how deque is different from inbuilt data structures like python dictionary, list and set , copy the full code given above, paste it into your IDE and experiment with the deque operations. Stay tuned for more informative articles.