Approach
We will implement using the concept of a doubly linked list. We will maintain two pointers - Front and Rear to keep track of the beginning and end of the queue. When we need to insert or delete elements from the beginning, we will appropriately tweak the Front pointer to make the necessary changes. The same goes with the Rear pointer usage.
We can maintain a variable size to keep track of the size of the data structure. In the case of insert statements, we will increase the size by one, and in the case of delete, we will decrease the size by one. We can use the value of the size variable to determine if the deque is empty or not.
Algorithm
We will implement each of the functionalities in the form of functions -
- Create a Node structure to represent a node in the doubly-linked list.
- Create a class Deque to represent the deque data structure to be implemented.
- Create front and rear pointers to keep track of the beginning and end of the deque and initialize the size variable with zero.
- Create the following functions as part of the class Deque.
insertFront
This function takes an integer as an argument. Create a new node in the doubly-linked list with value as the integer provided as the argument. Then execute the following statements -
IF front == NULL, then
rear = front = newNode
ELSE
newNode->next = front
front->prev = newNode
front = newNode
insertEnd
This function takes an integer as an argument. Create a new node in the doubly-linked list with value as the integer provided as the argument. Then execute the following statements -
IF rear == NULL, then
rear = front = newNode
ELSE
newNode->prev = front
rear->next = newNode
rear = newNode
deleteFront
Check if the deque is empty. If yes, return.
Node* temp = front
front = front->next
IF front == NULL
rear = NULL
ELSE
front->prev = NULL
Deallocate space for temp
deleteRear
Check if the deque is empty. If yes, return.
Node* temp = rear
rear = rear->prev
IF rear == NULL
front = NULL
ELSE
rear->next = NULL
Deallocate space for temp
isEmpty
Return if the deque is empty based on the value of the size variable.
getFront
If the queue is empty, output a garbage value. Otherwise, return the value of the node pointed to by the front pointer.
getRear
If the queue is empty, output a garbage value. Otherwise, return the value of the node pointed to by the rear pointer.
C++ Program
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int value;
Node *prev, *next;
// prev and next pointers to point to the previous and next element in the deque.
};
// Function to create a new node in the deque or doubly-linked list.
Node* createnode(int value)
{
Node* newNode = new Node();
newNode->value = value;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
class Deque
{
Node* front;
Node* rear;
int Size;
public:
Deque()
{
front = rear = NULL;
Size = 0;
}
// Operations/Functionalities on Deque.
void insertFront(int value);
void insertRear(int value);
void deleteFront();
void deleteRear();
int getFront();
int getRear();
int size();
bool isEmpty();
};
// This function checks if the deque is empty.
bool Deque::isEmpty()
{
if(Size == 0){
return true;
}
return false;
}
// Function to return the size of the deque.
int Deque::size()
{
return Size;
}
// Function to insert an element at the beginning of the deque.
void Deque::insertFront(int value)
{
Node* newNode = createnode(value);
// If deque is empty then update the front and rear pointers.
if (front == NULL){
rear = front = newNode;
}
// Otherwise insert at the beginning of the deque according to the algorithm described above.
else
{
newNode->next = front;
front->prev = newNode;
front = newNode;
}
// Increase the size of the queue by one.
Size++;
}
// Function to insert an element at the end of the deque.
void Deque::insertRear(int value)
{
Node* newNode = createnode(value);
// If deque is empty then update the front and rear pointers.
if (rear == NULL)
front = rear = newNode;
// Otherwise insert at the end of the deque according to the algorithm described above.
else
{
newNode->prev = rear;
rear->next = newNode;
rear = newNode;
}
// Increase the size of the queue by one.
Size++;
}
// Function to delete the element from the front end of the deque.
void Deque::deleteFront()
{
// Check if the deque is empty.
if (isEmpty())
cout << "UnderFlow\n";
// Otherwise, delete the element at the beginning of the deque according to the algorithm described above.
else
{
Node* temp = front;
front = front->next;
// If only one element was present in the deque.
if (front == NULL)
rear = NULL;
else
front->prev = NULL;
free(temp);
// Decrease the size of the deque by one.
Size--;
}
}
// Function to delete the element from the rear end of the deque.
void Deque::deleteRear()
{
// Check if the deque is empty.
if (isEmpty())
cout << "UnderFlow\n";
// Otherwise delete the element at the end of the deque according to the algorithm described above.
else
{
Node* temp = rear;
rear = rear->prev;
// If only one element was present in the deque.
if (rear == NULL)
front = NULL;
else
rear->next = NULL;
free(temp);
// Decrease the size of the deque by one.
Size--;
}
}
// Function to return the element at the front of the deque.
int Deque::getFront()
{
// If deque is empty, then return garbage value.
if (isEmpty())
return -1; // garbage value
return front->value;
}
// Function to return the element at the back of the deque.
int Deque::getRear()
{
// If deque is empty, then returns
// garbage value
if (isEmpty())
return -1;
return rear->value;
}
int main(){
Deque deq;
// keep taking input till the user ends the program.
printf("To exit, Enter 9.\n");
while(true){
int operation;
cin>>operation;
if(operation <= 2){
int val; cin>>val;
if(operation == 1){
deq.insertFront(val);
}
else deq.insertRear(val);
}
else{
if(operation == 3){
deq.deleteFront();
}
else if(operation == 4){
deq.deleteRear();
}
else if(operation == 5){
if(deq.getFront() != -1)
cout<<"Front element: "<<deq.getFront()<<endl;
else cout<<"The deque is empty"<<endl;
}
else if(operation == 6){
if(deq.getRear() != -1)
cout<<"Rear element: "<<deq.getRear()<<endl;
else cout<<"The deque is empty"<<endl;
}
else if(operation == 7){
if(deq.isEmpty()) cout<<"The deque is empty"<<endl;
else cout<<"The deque is not empty"<<endl;
}
else if(operation == 8){
cout<<"The size of the deque is "<<deq.size()<<endl;
}
else break;
}
}
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
Output

Complexity Analysis
Time Complexity
The time complexities of the various functions are -
- insertFront - O(1)
- insertRear - O(1)
- deleteFront - O(1)
- deleteRear - O(1)
- getFront - O(1)
- getRear - O(1)
- isEmpty - O(1)
- size - O(1)
- erase - O(n)
Space Complexity
The space complexity is O(n) to hold the deque.
Read about Application of Queue in Data Structure here.
Frequently Asked Questions (FAQs)
What is the time complexity for insertion or deletion of an element either at the head or tail of a Doubly Linked List?
The insertion or deletion operation is performed in a constant time i.e. O(1) at both the head and tail of the linked list.
How can you make a Doubly Linked List into a Circular Linked List?
The previous pointer or here the rear pointer of the head node should point to the tail node as well as the next pointer or here the front pointer of the tail node should point to the head node instead of being NULL creating a closed-loop and thus making a Doubly Linked List into Circular Linked List.
Conclusion
One of the most significant concepts and data structures to grasp while preparing for interviews is the linked list. Knowing how to use a linked list effectively can be quite beneficial in coding interviews. In this blog, we built a deque data structure using a doubly-linked list. We saw how to handle delete operations in a doubly-linked list using a straightforward algorithm.
Recommended Articles
There are many more applications of doubly-linked lists. Hence learning never stops, and there is a lot more to learn. So check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, etc. along with some Contests, Test Series, and Interview Experiences only on Coding Ninjas Studio.