We will see what is deque data structure and how to implement deque with the doubly linked list in javascript.
Deque or Double-ended queue is a generalized version of queue in which data can be added or removed from both the ends.
It works like both a stack and queue and can be used as any of them.
We have already implemented the Deque data structure with the circular array, but here we will see how can we implement deque with a doubly-linked list.
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.
function dequeWithDLL() {
//create a doubly linked list object
let dll = new doubleLinkedList();
//other methods go here
}
Adding an item on the front
To add a new item on the front we just need to append the data in the list.
//Add an item on the front
this.insertFront = (elm) => {
dll.append(elm);
return true;
}
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.
//Add an item on the back
this.insertBack = (elm) => {
let length = dll.size();
dll.insert(length, elm);
return true;
}
Remove an item from the front
To remove the item from front we just need to delete the head of the list.
//Remove item from the front
this.removeFront = () => {
return dll.deleteHead();
}
Remove an item from the back
To remove the item from back we just need to delete the tail of the list.
//Remove item from the back
this.removeBack = () => {
return dll.deleteTail();
}
Get the first element from the front
To peek the first element of the the front just get the head and return its element.
//Peek the front element
this.getFront = () => {
let head = dll.getHead();
return head && head.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.
//Peek the back element
this.getBack = () => {
let tail = dll.getTail();
return tail && tail.element;
}
Check if deque is empty
//Check if empty
this.isEmpty = () => {
return dll.isEmpty();
}
Get the size of the deque
//Get the size
this.size = () => {
return dll.size();
}
Clear the deque
//Clear the deque
this.clear = () => {
dll = new doubleLinkedList();
}
Get the deque element as a string
//Convert to the string
//From front to back
this.toString = () => {
if (this.isEmpty()) {
return '';
}
let current = dll.getHead();
let objString = '';
while(current){
objString = current.element + ' ' + objString;
current = current.next;
}
return objString.trim();
}
Complete code of deque with doubly linked list
function dequeWithDLL() {
let dll = new doubleLinkedList();
//Add an item on the front
this.insertFront = (elm) => {
dll.append(elm);
return true;
}
//Add an item on the back
this.insertBack = (elm) => {
let length = dll.size();
dll.insert(length, elm);
return true;
}
//Remove item from the front
this.removeFront = () => {
return dll.deleteHead();
}
//Remove item from the back
this.removeBack = () => {
return dll.deleteTail();
}
//Peek the front element
this.getFront = () => {
let head = dll.getHead();
return head && head.element;
}
//Peek the back element
this.getBack = () => {
let tail = dll.getTail();
return tail && tail.element;
}
//Check if empty
this.isEmpty = () => {
return dll.isEmpty();
}
//Get the size
this.size = () => {
return dll.size();
}
//Clear the deque
this.clear = () => {
dll = new doubleLinkedList();
}
//Convert to the string
//From front to back
this.toString = () => {
if (this.isEmpty()) {
return '';
}
let current = dll.getHead();
let objString = '';
while(current){
objString = current.element + ' ' + objString;
current = current.next;
}
return objString.trim();
}
}
Input: let deque = new dequeWithDLL(); deque.insertBack(5); deque.insertBack(10); console.log(deque.getBack()); deque.removeBack(); console.log(deque.getBack()); deque.insertFront(15); console.log(deque.getFront()); deque.removeFront(); console.log(deque.getFront()); console.log(deque.toString()); Output: 5 5 15 "15"
Making the properties and methods private with closure and IIFE (Immediately Invoked Function Expression).
let dequeWithDLL = (function(){
return function DequeWithDLL() {
let dll = new doubleLinkedList();
//Add an item on the front
this.insertFront = (elm) => {
dll.append(elm);
return true;
}
//Add an item on the back
this.insertBack = (elm) => {
let length = dll.size();
dll.insert(length, elm);
return true;
}
//Remove item from the front
this.removeFront = () => {
return dll.deleteHead();
}
//Remove item from the back
this.removeBack = () => {
return dll.deleteTail();
}
//Peek the front element
this.getFront = () => {
let head = dll.getHead();
return head && head.element;
}
//Peek the back element
this.getBack = () => {
let tail = dll.getTail();
return tail && tail.element;
}
//Check if empty
this.isEmpty = () => {
return dll.isEmpty();
}
//Get the size
this.size = () => {
return dll.size();
}
//Clear the deque
this.clear = () => {
dll = new doubleLinkedList();
}
//Convert to the string
//From front to back
this.toString = () => {
if (this.isEmpty()) {
return '';
}
let current = dll.getHead();
let objString = '';
while(current){
objString = current.element + ' ' + objString;
current = current.next;
}
return objString.trim();
}
}
}());
Input: let deque = new dequeWithDLL(); deque.insertBack(5); deque.insertBack(10); console.log(deque.getBack()); deque.removeBack(); console.log(deque.getBack()); deque.insertFront(15); console.log(deque.getFront()); deque.removeFront(); console.log(deque.getFront()); console.log(deque.toString()); Output: 5 5 15 "15"
Class based implementation of deque with doubly linked list
class dequeWithDLL {
constructor(){
this.dll = new doubleLinkedList();
}
//Add an item on the front
insertFront = (elm) => {
this.dll.append(elm);
return true;
}
//Add an item on the back
insertBack = (elm) => {
let length = this.dll.size();
this.dll.insert(length, elm);
return true;
}
//Remove item from the front
removeFront = () => {
return this.dll.deleteHead();
}
//Remove item from the back
removeBack = () => {
return this.dll.deleteTail();
}
//Peek the front element
getFront = () => {
let head = this.dll.getHead();
return head && head.element;
}
//Peek the back element
getBack = () => {
let tail = this.dll.getTail();
return tail && tail.element;
}
//Check if empty
isEmpty = () => {
return this.dll.isEmpty();
}
//Get the size
size = () => {
return this.dll.size();
}
//Clear the deque
clear = () => {
this.dll = new doubleLinkedList();
}
//Convert to the string
//From front to back
toString = () => {
if (this.isEmpty()) {
return '';
}
let current = this.dll.getHead();
let objString = '';
while(current){
objString = current.element + ' ' + objString;
current = current.next;
}
return objString.trim();
}
}
Input: let deque = new dequeWithDLL(); deque.insertBack(5); deque.insertBack(10); console.log(deque.getBack()); deque.removeBack(); console.log(deque.getBack()); deque.insertFront(15); console.log(deque.getFront()); deque.removeFront(); console.log(deque.getFront()); console.log(deque.toString()); Output: 5 5 15 "15"
Time Complexity
| # | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Average | Θ(1) | Θ(N) | Θ(1) | Θ(1) |
| Worst | O(1) | O(N) | O(1) | O(1) |
Space Complexity
| # | space |
|---|---|
| Worst | O(N) |