• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar
PythonForBeginners.com

PythonForBeginners.com

Learn By Example

  • Home
  • Learn Python
    • Python Tutorial
  • Categories
    • Basics
    • Lists
    • Dictionary
    • Code Snippets
    • Comments
    • Modules
    • API
    • Beautiful Soup
    • Cheatsheet
    • Games
    • Loops
  • Python Courses
    • Python 3 For Beginners
You are here: Home / deque / Implement Deque in Python

Implement Deque in Python

Author: Aditya Raj
Last Updated: June 3, 2021

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.

Related

Recommended Python Training

Course: Python 3 For Beginners

Over 15 hours of video content with guided instruction for beginners. Learn how to create real world applications and master the basics.

Enroll Now

Filed Under: deque Author: Aditya Raj

More Python Topics

API Argv Basics Beautiful Soup bitly Cheatsheet Code Code Snippets Command Line Comments Concatenation crawler Data Structures Data Types deque Development Dictionary Dictionary Data Structure In Python Error Handling Exceptions Filehandling Files Functions Games GUI Json Lists Loops Mechanzie Modules Modules In Python Mysql OS pip Python Python On The Web Python Strings Queue Requests Scraping Scripts Split Strings System & OS urllib2

Primary Sidebar

Menu

  • Basics
  • Cheatsheet
  • Code Snippets
  • Development
  • Dictionary
  • Error Handling
  • Lists
  • Loops
  • Modules
  • Scripts
  • Strings
  • System & OS
  • Web

Get Our Free Guide To Learning Python

Most Popular Content

  • Reading and Writing Files in Python
  • Python Dictionary – How To Create Dictionaries In Python
  • How to use Split in Python
  • Python String Concatenation and Formatting
  • List Comprehensions in Python
  • How to Use sys.argv in Python?
  • How to use comments in Python
  • Try and Except in Python

Recent Posts

  • Pandas Append Row to DataFrame
  • Convert String to DataFrame in Python
  • Pandas DataFrame to List in Python
  • Solved: Dataframe Constructor Not Properly Called Error in Pandas
  • Overwrite a File in Python

Copyright © 2012–2023 · PythonForBeginners.com

  • Home
  • Contact Us
  • Privacy Policy
  • Write For Us