Implementation of Deque using doubly linked list

Deque or Double Ended Queue is a generalized version of Queue data structure that allows insert and delete at both ends. In previous post Implementation of Deque using circular array has been discussed. Now in this post we see how we implement Deque using Doubly Linked List.

Operations on Deque :

Mainly the following four basic operations are performed on queue :

insertFront() : Adds an item at the front of Deque.
insertRear()  : Adds an item at the rear of Deque.
deleteFront() : Deletes an item from front of Deque.
deleteRear()  : Deletes an item from rear of Deque.

In addition to above operations, following operations are also supported :

getFront() : Gets the front item from queue.
getRear()  : Gets the last item from queue.
isEmpty()  : Checks whether Deque is empty or not.
size()     : Gets number of elements in Deque.
erase()    : Deletes all the elements from Deque.

Doubly Linked List Representation of Deque :
For implementing deque, we need to keep track of two pointers, front and rear. We enqueue (push) an item at the rear or the front end of deque and dequeue(pop) an item from both rear and front end.

Working :
Declare two pointers front and rear of type Node, where Node represents the structure of a node of a doubly linked list. Initialize both of them with value NULL.

Insertion at Front end :

1. Allocate space for a newNode of doubly linked list.
2. IF newNode == NULL, then
3.     print "Overflow"
4. ELSE
5.     IF front == NULL, then
6.         rear = front = newNode
7.     ELSE
8.         newNode->next = front
9.       front->prev = newNode
10.        front = newNode

Insertion at Rear end :

1. Allocate space for a newNode of doubly linked list.
2. IF newNode == NULL, then
3.     print "Overflow"
4. ELSE
5.     IF rear == NULL, then
6.         front = rear = newNode
7.     ELSE
8.         newNode->prev = rear
9.       rear->next = newNode
10.        rear = newNode

Deletion from Front end :

1. IF front == NULL
2.     print "Underflow"
3. ELSE
4.     Initialize temp = front
5.     front = front->next
6.     IF front == NULL
7.         rear = NULL
8.     ELSE
9.         front->prev = NULL
10     Deallocate space for temp

Deletion from Rear end :

1. IF front == NULL
2.     print "Underflow"
3. ELSE
4.     Initialize temp = rear
5.     rear = rear->prev
6.     IF rear == NULL
7.         front = NULL
8.     ELSE
9.         rear->next = NULL
10     Deallocate space for temp

Implementation:

CPP

// C++ implementation of Deque using 
// doubly linked list 
#include <bits/stdc++.h> 
  
using namespace std; 
  
// Node of a doubly linked list 
struct Node { 
    int data; 
    Node *prev, *next; 
    // Function to get a new node 
    static Node* getnode(int data) 
    { 
        Node* newNode = (Node*)malloc(sizeof(Node)); 
        newNode->data = data; 
        newNode->prev = newNode->next = NULL; 
        return newNode; 
    } 
}; 
  
// A structure to represent a deque 
class Deque { 
    Node* front; 
    Node* rear; 
    int Size; 
  
public: 
    Deque() 
    { 
        front = rear = NULL; 
        Size = 0; 
    } 
  
    // Operations on Deque 
    void insertFront(int data); 
    void insertRear(int data); 
    void deleteFront(); 
    void deleteRear(); 
    int getFront(); 
    int getRear(); 
    int size(); 
    bool isEmpty(); 
    void erase(); 
}; 
  
// Function to check whether deque 
// is empty or not 
bool Deque::isEmpty() { return (front == NULL); } 
  
// Function to return the number of 
// elements in the deque 
int Deque::size() { return Size; } 
  
// Function to insert an element 
// at the front end 
void Deque::insertFront(int data) 
{ 
    Node* newNode = Node::getnode(data); 
    // If true then new element cannot be added 
    // and it is an 'Overflow' condition 
    if (newNode == NULL) 
        cout << "OverFlow\n"; 
    else { 
        // If deque is empty 
        if (front == NULL) 
            rear = front = newNode; 
  
        // Inserts node at the front end 
        else { 
            newNode->next = front; 
            front->prev = newNode; 
            front = newNode; 
        } 
  
        // Increments count of elements by 1 
        Size++; 
    } 
} 
  
// Function to insert an element 
// at the rear end 
void Deque::insertRear(int data) 
{ 
    Node* newNode = Node::getnode(data); 
    // If true then new element cannot be added 
    // and it is an 'Overflow' condition 
    if (newNode == NULL) 
        cout << "OverFlow\n"; 
    else { 
        // If deque is empty 
        if (rear == NULL) 
            front = rear = newNode; 
  
        // Inserts node at the rear end 
        else { 
            newNode->prev = rear; 
            rear->next = newNode; 
            rear = newNode; 
        } 
  
        Size++; 
    } 
} 
  
// Function to delete the element 
// from the front end 
void Deque::deleteFront() 
{ 
    // If deque is empty then 
    // 'Underflow' condition 
    if (isEmpty()) 
        cout << "UnderFlow\n"; 
  
    // Deletes the node from the front end and makes 
    // the adjustment in the links 
    else { 
        Node* temp = front; 
        front = front->next; 
  
        // If only one element was present 
        if (front == NULL) 
            rear = NULL; 
        else
            front->prev = NULL; 
        free(temp); 
  
        // Decrements count of elements by 1 
        Size--; 
    } 
} 
  
// Function to delete the element 
// from the rear end 
void Deque::deleteRear() 
{ 
    // If deque is empty then 
    // 'Underflow' condition 
    if (isEmpty()) 
        cout << "UnderFlow\n"; 
  
    // Deletes the node from the rear end and makes 
    // the adjustment in the links 
    else { 
        Node* temp = rear; 
        rear = rear->prev; 
  
        // If only one element was present 
        if (rear == NULL) 
            front = NULL; 
        else
            rear->next = NULL; 
        free(temp); 
  
        // Decrements count of elements by 1 
        Size--; 
    } 
} 
  
// Function to return the element 
// at the front end 
int Deque::getFront() 
{ 
    // If deque is empty, then returns 
    // garbage value 
    if (isEmpty()) 
        return -1; 
    return front->data; 
} 
  
// Function to return the element 
// at the rear end 
int Deque::getRear() 
{ 
    // If deque is empty, then returns 
    // garbage value 
    if (isEmpty()) 
        return -1; 
    return rear->data; 
} 
  
// Function to delete all the elements 
// from Deque 
void Deque::erase() 
{ 
    rear = NULL; 
    while (front != NULL) { 
        Node* temp = front; 
        front = front->next; 
        free(temp); 
    } 
    Size = 0; 
} 
  
// Driver program to test above 
int main() 
{ 
    Deque dq; 
    cout << "Insert element '5' at rear end\n"; 
    dq.insertRear(5); 
  
    cout << "Insert element '10' at rear end\n"; 
    dq.insertRear(10); 
  
    cout << "Rear end element: " << dq.getRear() << endl; 
  
    dq.deleteRear(); 
    cout << "After deleting rear element new rear"
         << " is: " << dq.getRear() << endl; 
  
    cout << "Inserting element '15' at front end \n"; 
    dq.insertFront(15); 
  
    cout << "Front end element: " << dq.getFront() << endl; 
  
    cout << "Number of elements in Deque: " << dq.size() 
         << endl; 
  
    dq.deleteFront(); 
    cout << "After deleting front element new "
         << "front is: " << dq.getFront() << endl; 
  
    return 0; 
}

Java

// Java implementation of Deque using 
// doubly linked list 
import java.util.*; 
class GFG { 
  
    // Node of a doubly linked list 
    static class Node { 
        int data; 
        Node prev, next; 
  
        // Function to get a new node 
        static Node getnode(int data) 
        { 
            Node newNode = new Node(); 
            newNode.data = data; 
            newNode.prev = newNode.next = null; 
            return newNode; 
        } 
    }; 
  
    // A structure to represent a deque 
    static class Deque { 
        Node front; 
        Node rear; 
        int Size; 
  
        Deque() 
        { 
            front = rear = null; 
            Size = 0; 
        } 
  
        // Function to check whether deque 
        // is empty or not 
        boolean isEmpty() { return (front == null); } 
  
        // Function to return the number of 
        // elements in the deque 
        int size() { return Size; } 
  
        // Function to insert an element 
        // at the front end 
        void insertFront(int data) 
        { 
            Node newNode = Node.getnode(data); 
            // If true then new element cannot be added 
            // and it is an 'Overflow' condition 
            if (newNode == null) 
                System.out.print("OverFlow\n"); 
            else { 
                // If deque is empty 
                if (front == null) 
                    rear = front = newNode; 
  
                // Inserts node at the front end 
                else { 
                    newNode.next = front; 
                    front.prev = newNode; 
                    front = newNode; 
                } 
  
                // Increments count of elements by 1 
                Size++; 
            } 
        } 
  
        // Function to insert an element 
        // at the rear end 
        void insertRear(int data) 
        { 
            Node newNode = Node.getnode(data); 
            // If true then new element cannot be added 
            // and it is an 'Overflow' condition 
            if (newNode == null) 
                System.out.print("OverFlow\n"); 
            else { 
                // If deque is empty 
                if (rear == null) 
                    front = rear = newNode; 
  
                // Inserts node at the rear end 
                else { 
                    newNode.prev = rear; 
                    rear.next = newNode; 
                    rear = newNode; 
                } 
  
                Size++; 
            } 
        } 
  
        // Function to delete the element 
        // from the front end 
        void deleteFront() 
        { 
            // If deque is empty then 
            // 'Underflow' condition 
            if (isEmpty()) 
                System.out.print("UnderFlow\n"); 
  
            // Deletes the node from the front end and makes 
            // the adjustment in the links 
            else { 
                Node temp = front; 
                front = front.next; 
  
                // If only one element was present 
                if (front == null) 
                    rear = null; 
                else
                    front.prev = null; 
  
                // Decrements count of elements by 1 
                Size--; 
            } 
        } 
  
        // Function to delete the element 
        // from the rear end 
        void deleteRear() 
        { 
            // If deque is empty then 
            // 'Underflow' condition 
            if (isEmpty()) 
                System.out.print("UnderFlow\n"); 
  
            // Deletes the node from the rear end and makes 
            // the adjustment in the links 
            else { 
                Node temp = rear; 
                rear = rear.prev; 
  
                // If only one element was present 
                if (rear == null) 
                    front = null; 
                else
                    rear.next = null; 
  
                // Decrements count of elements by 1 
                Size--; 
            } 
        } 
  
        // Function to return the element 
        // at the front end 
        int getFront() 
        { 
            // If deque is empty, then returns 
            // garbage value 
            if (isEmpty()) 
                return -1; 
            return front.data; 
        } 
  
        // Function to return the element 
        // at the rear end 
        int getRear() 
        { 
  
            // If deque is empty, then returns 
            // garbage value 
            if (isEmpty()) 
                return -1; 
            return rear.data; 
        } 
  
        // Function to delete all the elements 
        // from Deque 
        void erase() 
        { 
            rear = null; 
            while (front != null) { 
                Node temp = front; 
                front = front.next; 
            } 
            Size = 0; 
        } 
    } 
  
    // Driver program to test above 
    public static void main(String[] args) 
    { 
        Deque dq = new Deque(); 
        System.out.print( 
            "Insert element '5' at rear end\n"); 
        dq.insertRear(5); 
  
        System.out.print( 
            "Insert element '10' at rear end\n"); 
        dq.insertRear(10); 
        System.out.print("Rear end element: " + dq.getRear() 
                         + "\n"); 
        dq.deleteRear(); 
        System.out.print( 
            "After deleting rear element new rear"
            + " is: " + dq.getRear() + "\n"); 
        System.out.print( 
            "Inserting element '15' at front end \n"); 
        dq.insertFront(15); 
        System.out.print( 
            "Front end element: " + dq.getFront() + "\n"); 
  
        System.out.print("Number of elements in Deque: "
                         + dq.size() + "\n"); 
        dq.deleteFront(); 
        System.out.print("After deleting front element new "
                         + "front is: " + dq.getFront() 
                         + "\n"); 
    } 
} 
  
// This code is contributed by gauravrajput1

Python3

class GFG: 
    # Node of a doubly linked list 
    class Node: 
        data = 0
        prev = None
        next = None
  
        # Function to get a new node 
        @staticmethod
        def getnode(data): 
            newNode = GFG.Node() 
            newNode.data = data 
            newNode.prev = None
            newNode.next = None
            return newNode 
  
    # A structure to represent a deque 
    class Deque: 
        front = None
        rear = None
        Size = 0
  
        def __init__(self): 
            self.front = None
            self.rear = None
            self.Size = 0
  
        # Function to check whether deque 
        # is empty or not 
        def isEmpty(self): 
            return (self.front == None) 
  
        # Function to return the number of 
        # elements in the deque 
        def size(self): 
            return self.Size 
  
        # Function to insert an element 
        # at the front end 
        def insertFront(self, data): 
            newNode = GFG.Node.getnode(data) 
  
            # If true then new element cannot be added 
            # and it is an 'Overflow' condition 
            if (newNode == None): 
                print("OverFlow\n", end="") 
            else: 
  
                # If deque is empty 
                if (self.front == None): 
                    self.rear = newNode 
                    self.front = newNode 
                else: 
                    newNode.next = self.front 
                    self.front.prev = newNode 
                    self.front = newNode 
  
                # Increments count of elements by 1 
                self.Size += 1
  
        # Function to insert an element 
        # at the rear end 
        def insertRear(self, data): 
            newNode = GFG.Node.getnode(data) 
  
            # If true then new element cannot be added 
            # and it is an 'Overflow' condition 
            if (newNode == None): 
                print("OverFlow\n", end="") 
            else: 
  
                # If deque is empty 
                if (self.rear == None): 
                    self.front = newNode 
                    self.rear = newNode 
                else: 
                    newNode.prev = self.rear 
                    self.rear.next = newNode 
                    self.rear = newNode 
                self.Size += 1
  
        # Function to delete the element 
        # from the front end 
        def deleteFront(self): 
  
            # If deque is empty then 
            # 'Underflow' condition 
            if (self.isEmpty()): 
                print("UnderFlow\n", end="") 
            else: 
                temp = self.front 
                self.front = self.front.next
  
                # If only one element was present 
                if (self.front == None): 
                    self.rear = None
                else: 
                    self.front.prev = None
  
                # Decrements count of elements by 1 
                self.Size -= 1
  
        # Function to delete the element 
        # from the rear end 
        def deleteRear(self): 
  
            # If deque is empty then 
            # 'Underflow' condition 
            if (self.isEmpty()): 
                print("UnderFlow\n", end="") 
            else: 
                temp = self.rear 
                self.rear = self.rear.prev 
  
                # If only one element was present 
                if (self.rear == None): 
                    self.front = None
                else: 
                    self.rear.next = None
  
                # Decrements count of elements by 1 
                self.Size -= 1
  
        # Function to return the element 
        # at the front end 
        def getFront(self): 
  
            # If deque is empty, then returns 
            # garbage value 
            if (self.isEmpty()): 
                return -1
            return self.front.data 
  
        # Function to return the element 
        # at the rear end 
        def getRear(self): 
  
            # If deque is empty, then returns 
            # garbage value 
            if (self.isEmpty()): 
                return -1
            return self.rear.data 
  
        # Function to delete all the elements 
        # from Deque 
        def erase(self): 
            self.rear = None
            while (self.front != None): 
                temp = self.front 
                self.front = self.front.next
            self.Size = 0
  
    # Driver program to test above 
    @staticmethod
    def main(args): 
        dq = GFG.Deque() 
        print("Insert element \'5\' at rear end\n", end="") 
        dq.insertRear(5) 
        print("Insert element \'10\' at rear end\n", end="") 
        dq.insertRear(10) 
        print("Rear end element: " + str(dq.getRear()) + "\n", end="") 
        dq.deleteRear() 
        print("After deleting rear element new rear" +
              " is: " + str(dq.getRear()) + "\n", end="") 
        print("Inserting element \'15\' at front end \n", end="") 
        dq.insertFront(15) 
        print("Front end element: " + str(dq.getFront()) + "\n", end="") 
        print("Number of elements in Deque: " + str(dq.size()) + "\n", end="") 
        dq.deleteFront() 
        print("After deleting front element new " +
              "front is: " + str(dq.getFront()) + "\n", end="") 
  
  
if __name__ == "__main__": 
    GFG.main([]) 
  
    # This code is contributed by aadityaburujwale. 

Javascript

// Javascript implementation of Deque using 
// Node of a doubly linked list 
class Node { 
    data = 0; 
    prev = null; 
    next = null; 
  
    // Function to get a new node 
    static getnode(data) { 
        const newNode = new Node(); 
        newNode.data = data; 
        newNode.prev = null; 
        newNode.next = null; 
        return newNode; 
    } 
} 
  
// A structure to represent a deque 
class Deque { 
    front = null; 
    rear = null; 
    size = 0; 
  
    constructor() { 
        this.front = null; 
        this.rear = null; 
        this.size = 0; 
    } 
  
    // Function to check whether deque 
    // is empty or not 
    isEmpty() { 
        return this.front === null; 
    } 
  
    // Function to return the number of 
    // elements in the deque 
    size() { 
        return this.size; 
    } 
  
    // Function to insert an element 
    // at the front end 
    insertFront(data) { 
        const newNode = Node.getnode(data); 
  
        // If true then new element cannot be added 
        // and it is an 'Overflow' condition 
        if (newNode === null) { 
            console.log("OverFlow\n"); 
        } else { 
            // If deque is empty 
            if (this.front === null) { 
                this.rear = newNode; 
                this.front = newNode; 
            } else { 
                newNode.next = this.front; 
                this.front.prev = newNode; 
                this.front = newNode; 
            } 
  
            // Increments count of elements by 1 
            this.size += 1; 
        } 
    } 
  
    // Function to insert an element 
    // at the rear end 
    insertRear(data) { 
        const newNode = Node.getnode(data); 
  
        // If true then new element cannot be added 
        // and it is an 'Overflow' condition 
        if (newNode === null) { 
            console.log("OverFlow\n"); 
        } else { 
            // If deque is empty 
            if (this.rear === null) { 
                this.front = newNode; 
                this.rear = newNode; 
            } else { 
                newNode.prev = this.rear; 
                this.rear.next = newNode; 
                this.rear = newNode; 
            } 
            this.size += 1; 
        } 
    } 
  
    // Function to delete the element 
    // from the front end 
    deleteFront() { 
        // If deque is empty then 
        // 'Underflow' condition 
        if (this.isEmpty()) { 
            console.log("UnderFlow\n"); 
        } else { 
            const temp = this.front; 
            this.front = this.front.next; 
  
            // If only one element was present 
            if (this.front === null) { 
                this.rear = null; 
            } else { 
                this.front.prev = null; 
            } 
  
            // Decrements count of elements by 1 
            this.size -= 1; 
        } 
    } 
    deleteRear() { 
        // If deque is empty then 
        // 'Underflow' condition 
        if (this.isEmpty()) { 
            console.log("UnderFlow\n"); 
        } else { 
            const temp = this.rear; 
            this.rear = this.rear.prev; 
  
            // If only one element was present 
            if (this.rear === null) { 
                this.front = null; 
            } else { 
                this.rear.next = null; 
            } 
  
            // Decrements count of elements by 1 
            this.size -= 1; 
        } 
    } 
  
    // Function to return the element 
    // at the front end 
    getFront() { 
        // If deque is empty, then returns 
        // garbage value 
        if (this.isEmpty()) { 
            return -1; 
        } 
        return this.front.data; 
    } 
  
    // Function to return the element 
    // at the rear end 
    getRear() { 
        // If deque is empty, then returns 
        // garbage value 
        if (this.isEmpty()) { 
            return -1; 
        } 
        return this.rear.data; 
    } 
  
    // Function to delete all the elements 
    // from Deque 
    erase() { 
        this.rear = null; 
        while (this.front !== null) { 
            const temp = this.front; 
            this.front = this.front.next; 
        } 
        this.size = 0; 
    } 
} 
  
  
  
// Driver program to test the Deque class 
function main() { 
    // Create a Deque object 
    const dq = new Deque(); 
  
    console.log("Insert element '5' at rear end"); 
    dq.insertRear(5); 
  
    console.log("Insert element '10' at rear end"); 
    dq.insertRear(10); 
  
    console.log(`Rear end element: ${dq.getRear()}`); 
  
    dq.deleteRear(); 
    console.log(`After deleting rear element new rear is: ${dq.getRear()}`); 
  
    console.log("Inserting element '15' at front end"); 
    dq.insertFront(15); 
  
    console.log(`Front end element: ${dq.getFront()}`); 
  
    console.log(`Number of elements in Deque: ${dq.size}`); 
  
    dq.deleteFront(); 
    console.log(`After deleting front element new front is: ${dq.getFront()}`); 
} 
  
// Call the main function 
main(); 

Output

Insert element '5' at rear end
Insert element '10' at rear end
Rear end element: 10
After deleting rear element new rear is: 5
Inserting element '15' at front end 
Front end element: 15
Number of elements in Deque: 2
After deleting front element new front is: 5

Complexity Analysis:

Time Complexity : Time complexity of operations like insertFront(), insertRear(), deleteFront(), deleteRear() is O(1). The Time Complexity of erase() is O(n).
Auxiliary space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Implementation of Deque using doubly linked list

Operations on Deque :

CPP

Java

Python3

Javascript

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

The Boox Palma 2 Pro is a brilliant but unnecessarily complex e-reader

The Pixel Watch 4’s quiet upgrade that actually matters

Google Photos inches closer to bringing back this photo editing tool

5 surprising ways I use Google Maps that have nothing to do with navigation

EDITOR PICKS

The Boox Palma 2 Pro is a brilliant but unnecessarily complex e-reader

The Pixel Watch 4’s quiet upgrade that actually matters

Google Photos inches closer to bringing back this photo editing tool

POPULAR POSTS

The Boox Palma 2 Pro is a brilliant but unnecessarily complex e-reader

The Pixel Watch 4’s quiet upgrade that actually matters

Google Photos inches closer to bringing back this photo editing tool

POPULAR CATEGORY

ABOUT US

FOLLOW US