## Introduction

Deque, or Double Ended Queue, is a generalized Queue data structure that supports insert and delete from both ends. There are various ways to implement a deque, for example, using a circular array. In this blog, we will implement the different functionalities of the Deque data structure using a __Doubly Linked List____.__

## Problem Statement

You need to implement a deque data structure that supports the following operations/functionalities -

- Insert a value at the beginning
- Insert a value at the end
- Delete a value from the beginning
- Delete a value from the end
- Outputs the value at the beginning
- Outputs the value at the end
- Determines if it is empty
- Outputs its size

__Input Method__

To do an operation on the **deque** data structure, we will use the number assigned to that operation in the problem statement. For example -

i. to insert a value of 100 at the end of a deque, we will provide the following input -

2 100

ii. to output the size of the deque, we should provide the following input -

8

and so on.

**Input**

1 100

2 200

8

1 20

2 34

3

5

1 54

6

8

**Output**

The size of the deque: 2

Front element: 100

Rear element: 34

The size of the deque: 4

Before moving on to the solution try out a similar problem first: Implementation of Queue using Array or Singly Linked List

## 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;
}
```

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

- Circular Linked List
- Application of Linked List Data Structure
- Implement stack using a doubly-linked list
- Introduction and Implementation of Doubly Linked Lists
- Implementation Of Queue in Java using Array and Generics
- FIFO (First-In-First-Out) approach in Programming
- Features of Doubly Linked List
- Check if a Doubly-Linked List of Characters is a Palindrome or Not
- Advantages of Circular Queue
- Difference Between Array List and Linked List

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.