# Implementation of Deque using Doubly Linked List

Difficulty Level Medium
Frequently asked in Adobe Alation Amazon American Express DE Shaw Factset Fourkites GE Healthcare Google Oxigen Wallet Qualcomm Spotify Sprinklr UHG Optum Wooker Xome ZScaler

## Problem Statement

The problem “Implementation of Deque using Doubly Linked List” states that you need to implement the following functions of Deque or Doubly Ended Queue using a doubly linked list,

1. insertFront(x) : Add element x at the starting of Deque
2. insertEnd(x) : Add element x at the end of Deque
3. deleteFront() : Delete an element from the starting of Deque
4. deleteEnd() : Delete an element from the end of Deque
5. getFront() : Return the element at the starting of Deque
6. getEnd() : Return the element at the end of Deque
7. isEmpty() : Returns whether the Deque is empty
8. size() : Return the size of Deque
9. erase() : Delete all the elements of Deque

## Example

```insertFront(5)
insertEnd(10)
insertEnd(11)
insertFront(19)
getFront()
getEnd()
deleteEnd()
getEnd()
deleteFront()
getFront()
size()
isEmpty()
erase()
isEmpty()```
```19
11
10
5
2
false
true```

## Algorithm

To implement a Deque using a doubly linked list. We maintain two pointers front and rear, where front points to the front of a doubly linked list and rear points to the end. Also we need to maintain an integer size, that stores the number of nodes in the Deque.

To insert, delete, or get an element from starting we use the front pointer.

To insert, delete, or get an element from the end we use the rear pointer. ### insertFront(x)

To insert an element at the front of Deque, do the following

1. Create a new node with the required value and call it node.
2. If the front is null, make the front and rear equals node.
3. Else, insert the node before front and mark the node as a new front.
4. Increment size

Time Complexity O(1)

Pseudo Code

```Create a new node with required value and call it node
if (front == null) {
front = rear = node
} else {
node.next = front
front.prev = node
front = node
}
size++```

### insertEnd(x)

To insert an element at the end of Deque, do the following

1. Create a new node with required value and call it node.
2. If rear is null, make front and rear equals node.
3. Else, insert node after rear and mark the node as new rear.
4. Increment size

Time Complexity O(1)

Pseudo Code

```Create a new node with required value and call it node
if (rear == null) {
front = rear = node
} else {
rear.next = node
node.prev = rear
rear = node
}
size++```

### deleteFront()

To delete an element from front of Deque, do the following

1. If front is null, there is no element to delete, simply return.
2. If front is equals to rear, there is only 1 node, make front and rear null.
3. Else, make front equals front.next and delete front.prev
4. Decrement size

Time Complexity = O(1)

Pseudo Code

```if (front == null) {
return
}
if (front == rear) {
front = rear = null
} else {
temp = front
front = front.next
front.prev = null
deallocate space for temp
}
size--```

### deleteEnd()

To delete an element from the end of Deque, do the following

1. If rear is null, there is no node to delete, simply return.
2. If rear is equals to front, there is only one node, make front and rear null.
3. Else make rear as rear.prev and delete rear.next.
4. Decrement size

Time Complexity = O(1)

Pseudo Code

```if (rear == null) {
return;
}
if (rear == front) {
front = rear = null
} else {
temp = rear
rear = rear.prev
rear.next = null
deallocate space for temp
}
size--```

### getFront()

The front element of the Deque is pointed by front, so if front is not null return front.data

Time Complexity = O(1)

Pseudo Code

```if (front != null) {
return front.data
}
return -1```

### getEnd()

The end element of Deque is pointed by rear, so if rear is not null return rear.data

Time Complexity = O(1)

Pseudo Code

```if (rear != null) {
return rear.data
}
return -1```

### isEmpty()

If the Deque is empty both front and rear will be null, so if front is null return true, else return false.

Time Complexity = O(1)

Pseudo Code

```if (front == null) {
return true
}
return false```

### size()

The size of the Deque is stored in the variable named ‘size’, so simply return size.

Time Complexity = O(1)

Pseudo Code

`return size`

### erase()

Erasing Deque means deleting all the nodes of the Deque. To delete all the nodes do the following,

1. Set rear as null.
2. Create a temporary pointer temp, pointing to front.
3. Traverse in the Deque and repeat step 4, that is, while front is not null repeat step 4.
4. Set temp as front, front as front.next and deallocate space for temp.
5. Finally set temp as null and front as null and set size as 0.

Time Complexity = O(n), where n is the number of nodes in the Deque

Pseudo Code

```rear = null
Node temp = front
while (front != null) {
temp = front
front.prev = null
front = front.next
deallocate space for temp
}
temp = front = null
size = 0```

## Code

### Java code for Implementation of Deque using Doubly Linked List

```class DequeUsingDoublyLinkedList {
// class representing Node of a doubly linked list
static class Node {
int data;
Node next, prev;

public Node(int data) {
this.data = data;
}
}

// front points to start of Deque and rear points to the end of Deque
private static Node front = null;
private static Node rear = null;
private static int size = 0;

private static void insertFront(int x) {
// Create a new Node with required parameters
Node node = new Node(x);
if (front == null) {
// This is the first node to be inserted
front = rear = node;
} else {
// Add the node before front
node.next = front;
front.prev = node;
// update front
front = node;
}
// Increment size
size++;
}

private static void insertEnd(int x) {
// Create a new Node with required parameters
Node node = new Node(x);
if (rear == null) {
// This is the first node to be inserted
front = rear = node;
} else {
// Insert the node after rear
rear.next = node;
node.prev = rear;
// update rear
rear = node;
}
// Increment size
size++;
}
private static void deleteFront() {
if (front == null) {
// no node to delete
return;
}
if (front == rear) {
// only 1 node is present
front = rear = null;
} else {
// delete front and move front ahead
front = front.next;
front.prev = null;
// Garbage Collector will automatically delete first node
// as no pointer is pointing to it
}
// decrement size
size--;
}

private static void deleteEnd() {
if (rear == null) {
// no node to delete
return;
}
if (rear == front) {
// only 1 node is present
front = rear = null;
} else {
// delete rear and move rear backwards
rear = rear.prev;
rear.next = null;
// Garbage Collector will automatically delete last node
// as no pointer is pointing to it
}
// decrement size
size--;
}

private static int getFront() {
if (front != null) {
// front points to first element in Deque, return its data
return front.data;
}
// no node is present
return -1;
}

private static int getEnd() {
if (rear != null) {
// rear points to last element in Deque, return its data
return rear.data;
}
// no node is present
return -1;
}

private static boolean isEmpty() {
if (front == null) {
return true;
}
return false;
}

private static int size() {
return size;
}

private static void erase() {
// mark rear as null
rear = null;
// traverse the doubly linked list
while (front != null) {
// delete all the prev pointers
front.prev = null;
front = front.next;
}
// After this deque looks like
// a -> b -> c -> d ..., all the previous pointers are destroyed
// No pointer is pointing to a, so Garbage collector will delete the whole Deque

// set size as 0
size = 0;
}

public static void main(String[] args) {
// Example
insertFront(5);                 // 5
insertEnd(10);                  // 5 <-> 10
insertEnd(11);                  // 5 <-> 10 <-> 11
insertFront(19);                // 19 <-> 5 <-> 10 <-> 11
System.out.println(getFront());
System.out.println(getEnd());
deleteEnd();                    // 19 <-> 5 <-> 10
System.out.println(getEnd());
deleteFront();                  // 5 <-> 10
System.out.println(getFront());
System.out.println(size());
System.out.println(isEmpty());
erase();
System.out.println(isEmpty());
}
}```
```19
11
10
5
2
false
true```

### C++ Code for Implementation of Deque using Doubly Linked List

```#include<bits/stdc++.h>
using namespace std;

// class representing a tree node
class Node {
public:
int data;
Node *next;
Node *prev;

Node(int d) {
data = d;
next = NULL;
prev = NULL;
}
};

// function to create a new node
Node* newNode(int x) {
Node *node = new Node(x);
return node;
}

// front points to start of Deque and rear points to the end of Deque
Node *front = NULL;
Node *rear = NULL;
// Variable representing size of Deque
int Size = 0;

void insertFront(int x) {
// Create a new Node with required parameters
Node *node = newNode(x);
if (front == NULL) {
// This is the first node to be inserted
front = rear = node;
} else {
// Add the node before front
node->next = front;
front->prev = node;
// update front
front = node;
}
// Increment size
Size++;
}

void insertEnd(int x) {
// Create a new Node with required parameters
Node *node = newNode(x);
if (rear == NULL) {
// This is the first node to be inserted
front = rear = node;
} else {
// Insert the node after rear
node->prev = rear;
rear->next = node;
// update rear
rear = node;
}
// Increment size
Size++;
}

void deleteFront() {
if (front == NULL) {
// no node to delete
return;
}
if (front == rear) {
// only 1 node is present
front = rear = NULL;
} else {
// delete front and move front ahead
Node *temp = front;
front = front->next;
front->prev = NULL;
// deallocate the memory taken by temp
delete(temp);
}
// Decrement size
Size--;
}

void deleteEnd() {
if (rear == NULL) {
// no node to delete
return;
}
if (front == rear) {
// only 1 node is present
front = rear = NULL;
} else {
// delete rear and move rear backwards
Node *temp = rear;
rear = rear->prev;
rear->next = NULL;
// deallocate the memory taken by temp
delete(temp);
}
// Decrement size
Size--;
}

int getFront() {
if (front != NULL) {
return front->data;
}
return -1;
}

int getEnd() {
if (rear != NULL) {
return rear->data;
}
return -1;
}

int size() {
return Size;
}

bool isEmpty() {
if (front == NULL) {
return true;
}
return false;
}

void erase() {
// mark rear as null
rear = NULL;
// traverse the doubly linked list
while (front != NULL) {
Node *temp = front;
// delete all the prev pointers
front->prev = NULL;
front = front->next;
// Deallocate the memory taken by temp
delete(temp);
}
// Set size as 0
Size = 0;
}

int main() {
// Example
insertFront(5);                 // 5
insertEnd(10);                  // 5 <-> 10
insertEnd(11);                  // 5 <-> 10 <-> 11
insertFront(19);                // 19 <-> 5 <-> 10 <-> 11
cout<<getFront()<<endl;
cout<<getEnd()<<endl;
deleteEnd();                    // 19 <-> 5 <-> 10
cout<<getEnd()<<endl;
deleteFront();                  // 5 <-> 10
cout<<getFront()<<endl;
cout<<size()<<endl;
if (isEmpty()) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
erase();
if (isEmpty()) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}

return 0;
}```
```19
11
10
5
2
false
true```
Translate »