How would you implement deque using doubly linked list?

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

List of operations performed on Deque

• insertFront(): Inserts an element at the front.
• insertBack(): Inserts an element at the back.
• removeFront(): Removes an element from the front.
• removeBack(): Removes an element from the back.
• getFront(): Returns the element at the front.
• getBack(): Returns the element at the back.
• isEmpty(): Checks if the deque is empty or not.
• size(): Returns the size of the deque.
• clear(): Clears the deque.
• toString(): Returns all the elements concatenated as a string from front to back.

Implementing deque with doubly linked list

We will create a function and use the double linked list to create the Deque data structure.

Adding an item on the front

To add a new item on the front we just need to append the data in the list.

Adding an item on the back

To add a new item on the back we just need to insert the data after the last index.

Remove an item from the front

To remove the item from front we just need to delete the head of the list.

Remove an item from the back

To remove the item from back we just need to delete the tail of the list.

Get the first element from the front

To peek the first element of the the front just get the head and return its element.

Get the first element from the back

To peek the first element of the the back just get the tail and return its element.

Check if deque is empty

Get the size of the deque

Clear the deque

Get the deque element as a string

Deque Queue

Double-ended queue is an abstract data type. A deque represents a linear collection of elements that support insertion, retrieval and removal of elements at both ends. Dequeue, often abbreviated to deque.

OUTPUT: