Doubly Linked List implementation can be the preferred choice for Deque when the input data is dynamic and expected to grow larger. So, the Deque grows and shrinks based on the input data. However, the linked list implementation is slower than Array and requires additional memory.
See Deque Implementation using Circular Array to use with the static or limited data.
1. Representation
// Doubly list node representation
struct Node
{
int element;
Node* prev;
Node* next;
};
// Front ptr
Node* front = NULL;
// Rear ptr
Node* rear = NULL;
2. Implementation of Deque using Doubly Linked List in C++
/**
* C++ example to demonstrate Deque implementation using Doubly Linked List
*/
#include <iostream>
using namespace std;
// Doubly list node representation
struct Node
{
int element;
Node* prev;
Node* next;
};
/**
* Deque implementation using Doubly Linked List
*/
class Deque
{
private:
// Front ptr
Node* front;
// Rear ptr
Node* rear;
public:
// Constructor
Deque() : front(NULL), rear(NULL) {}
// Insert the new element at Front side
void insertFront(int element);
// Insert the new element at Rear side
void insertRear(int element);
// Delete the element from Front side
void deleteFront();
// Delete the element from Rear side
void deleteRear();
// Get the Front element
int getFront();
// Get the Rear element
int getRear();
// Print the Queue
void display(string msg);
};
// Insert the new element at Front side
void Deque::insertFront(int element) {
// Step 1. Create the new node
Node* new_node = new Node();
if (new_node == NULL) {
cout << "Memory overflow" << endl;
return;
}
new_node->element = element;
// Step 2. Check if the list is empty
if (front == NULL) {
// Step 3. If true, set Front and Rear to point the new node and return
new_node->prev = NULL;
new_node->next = NULL;
front = new_node;
rear = new_node;
return;
}
// Step 4. If false, link the new node at Front side
new_node->prev = NULL;
new_node->next = front;
front->prev = new_node;
// Step 5. Change the Front ptr to point the new node
front = new_node;
}
// Insert the new element at Rear side
void Deque::insertRear(int element) {
// Step 1. Create the new node
Node* new_node = new Node();
if (new_node == NULL) {
cout << "Memory overflow" << endl;
return;
}
new_node->element = element;
// Step 2. Check if the list is empty
if (front == NULL) {
// Step 3. If true, set Front and Rear to point the new node and return
new_node->prev = NULL;
new_node->next = NULL;
front = new_node;
rear = new_node;
return;
}
// Step 4. If false, link the new node at Rear side
new_node->prev = rear;
new_node->next = NULL;
rear->next = new_node;
// Step 5. Change the Rear ptr to point the new node
rear = new_node;
}
// Delete the element from Front side
void Deque::deleteFront() {
// Step 1. Check if the Deque is empty, and return if true.
if (front == NULL) {
cout << "Deque is empty" << endl;
return;
}
// Step 2. Remember the front node in a temporary pointer
Node* tmp = front;
// Step 3. Check if the Front and Rear are in the same position
// This occurs when deleting the last element
if (front == rear) {
// Step 4. If true, reset the Front and Rear pointers to NULL
front = NULL;
rear = NULL;
} else {
// Step 5. If false, move the Front to point the next node
front = front->next;
front->prev = NULL;
}
// Step 6. Delete the first node referenced by the temporary pointer
delete tmp;
}
// Delete the element from Rear side
void Deque::deleteRear() {
// Step 1. Check if the Deque is empty, and return if true.
if (front == NULL) {
cout << "Deque is empty" << endl;
return;
}
// Step 2. Remember the rear node in a temporary pointer
Node* tmp = rear;
// Step 3. Check if the Front and Rear are in the same position
// This occurs when deleting the last element
if (front == rear) {
// Step 4. If true, reset the Front and Rear pointers to NULL
front = NULL;
rear = NULL;
} else {
// Step 5. If false, move the Rear to point the previous node
rear = rear->prev;
rear->next = NULL;
}
// Step 6. Delete the last node referenced by the temporary pointer
delete tmp;
}
// Get the Front element
int Deque::getFront() {
if (front == NULL) {
cout << "Deque is empty" << endl;
return -1;
}
return front->element;
}
// Get the Rear element
int Deque::getRear() {
if (rear == NULL) {
cout << "Deque is empty" << endl;
return -1;
}
return rear->element;
}
// Print the Queue
void Deque::display(string msg) {
cout << msg << endl;
if (front == NULL) {
cout << "Deque is empty" << endl;
return;
}
cout << "FRONT --> ";
for (Node* p = front ; p != NULL ; p = p->next) {
cout << "[" << p->element << "]" << ((p != rear)? "--" : "");
}
cout << " <-- REAR" << endl << endl;
}
// The main function to begin the execution
int main()
{
// Create a Deque
Deque queue;
// Insert Front
queue.insertFront(5);
queue.insertFront(3);
queue.insertFront(1);
queue.display("Queue after inserting 5, 3, and 1 at the Front side");
// Insert Rear
queue.insertRear(10);
queue.insertRear(20);
queue.insertRear(30);
queue.display("Queue after inserting 10, 20, and 30 at the Rear side");
// Delete Front
int element = queue.getFront();
queue.deleteFront();
queue.display("Queue after deleting an element at Front");
// Delete Rear
element = queue.getRear();
queue.deleteRear();
queue.display("Queue after deleting an element at Rear");
}
Output
Queue after inserting 5, 3, and 1 at the Front side
FRONT --> [1]--[3]--[5] <-- REAR
Queue after inserting 10, 20, and 30 at the Rear side
FRONT --> [1]--[3]--[5]--[10]--[20]--[30] <-- REAR
Queue after deleting an element at Front
FRONT --> [3]--[5]--[10]--[20]--[30] <-- REAR
Queue after deleting an element at Rear
FRONT --> [3]--[5]--[10]--[20] <-- REAR3. Deque Operations using Doubly Linked List
3.1. Insert Front
Insert Front operation inserts a new node at the front side of Deque. This is accomplished by linking a new node at the Front side and updating the Front pointer.
Algorithm
- Create the new node.
- Check if the list is empty.
- If true,
- Initialize new Node’s Next and Prev to NULL.
- Set the Front and Rear to point to the new node
- Exit
- Otherwise, link the new node at the Front side
- Set the new node’s Prev to NULL.
- Set the new node’s Next to point to the front node.
- Change the front node’s Prev to point to the new node.
- Finally, update the Front to point to the new node.
Examples
The example demonstrates inserting the elements 5, and 3 in the front side of an empty Deque.
1. Initial Deque
- The initial Deque is empty. So the Front and Rear are set to NULL
2. Insert element (5) at the Front side
Create a new node for the element (5). Since the deque is empty, set Front and Rear to point to the new node.
3. Insert element (3) at the Front side
The deque is not empty, so link the new node at the Front side. Also, update the Front pointer to point the new node.
3.2. Insert Rear
Insert Rear inserts a new node at the rear side of Deque. This is accomplished by linking a new node at the rear side and updating the Rear pointer.
Algorithm
- Create the new node.
- Check if the list is empty.
- If true,
- Initialize new node’s Next and Prev to NULL.
- Set Front and Rear to point to the new node
- Exit
- Otherwise, link the new node at the Rear side
- Set new node’s Prev to point to the rear node.
- Set new node’s Next to NULL.
- Change the rear node’s Next to point to the new node.
- Finally, update the Rear to point to the new node.
Examples
The example demonstrates to insert the elements 10, and 20 in the following Deque.
1. Deque before insertRear
The Deque consists of two elements 3, and 5 inserted earlier.
2. Insert element (10) at the Rear side
Create a new node (10) and link at the Rear side. Then, update the Rear to point to the new node
3. Insert element (20) at the Rear side
Repeat the same procedure to link the new node (20) at the Rear side.
3.3. Delete Front
The Delete Front operation removes a node from the Front side of Deque. The Front pointer is updated to point to the next node.
Algorithm
- Check if the Deque is empty and return if true.
- Store the front node in a temporary pointer.
- Check for deleting the last node. The front and Rear are pointing to the same node.
- If true, make the list empty by resetting the Front and Rear to NULL.
- Otherwise, move the Front to the next node and disconnect the Prev link to the first node.
- Finally, delete the node referenced by the temporary pointer.
Examples
The example demonstrates the deletion of elements from the front side of Deque.
1. Deque before deleteFront
Initially, the deque consists of four elements (3, 5, 10, 20)
2. Delete node (3) from the Front side
Make the second node Front since we are deleting the first node.
3. Delete node (5) from the Front side
Repeat the same procedure and make the second node Front. Then delete the first node.
3.4. Delete Rear
The Delete Rear operation removes a node from the rear side of the Deque. The Rear pointer is updated to point to the previous node.
Algorithm
- Check if the Deque is empty and return if true.
- Store the front node in a temporary pointer.
- Check for deleting the last node. The front and Rear are pointing to the same node.
- If true, make the list empty. Reset the Front and Rear to NULL.
- Otherwise, move the Rear to the previous node and disconnect the Next link to the last node.
- Finally, delete the node referenced by the temporary pointer.
Examples
Let’s see the examples to delete the elements from the rear side of Deque.
1. Deque before deleteRear
The initial Deque consists of two elements 10 and 20.
2. Delete node (20) at the Rear side
Firstly, update the Rear pointer to point to the previous node. Then delete the last node.
3. Delete node (10) at the Rear side
Here, we need to delete the last node of Deque. So, set the Front and Rear to NULL and delete the last node.
