Skip to main content

Deque implementation using doubly linked list

The problem addressed in this code is the implementation of a Deque (Double-Ended Queue) using a doubly linked list in the C programming language. A Deque is a data structure that supports insertion and deletion of elements at both ends, allowing it to function as both a queue and a stack.

Problem Statement

The task is to create a Deque using a doubly linked list with the following operations:

  1. newDeque(): Creates a new Deque.
  2. isEmpty(q): Checks if the Deque is empty.
  3. isSize(q): Returns the number of elements in the Deque.
  4. insertFront(q, element): Inserts an element at the front of the Deque.
  5. insertRear(q, element): Inserts an element at the rear of the Deque.
  6. deleteFront(q): Removes an element from the front of the Deque.
  7. deleteRear(q): Removes an element from the rear of the Deque.
  8. peekFront(q): Returns the element at the front of the Deque without removing it.
  9. peekRear(q): Returns the element at the rear of the Deque without removing it.
  10. printDqueue(q): Displays the elements in the Deque.

Explanation with an Example

Imagine a restaurant line where customers can join the line at both the front and the back. Additionally, customers can leave the line from both ends. This scenario can be modeled using a Deque, allowing customers to choose where they want to join or leave the line.

Idea to Solve

The solution involves using a doubly linked list to implement a Deque. Elements can be inserted at both the front and the rear of the list, and they can be removed from both ends as well.

Pseudocode

Structure QNode:
    element
    next
    prev

Structure Deque:
    front
    rear
    size

newDeque():
    Create and initialize a new Deque
    Return the new Deque

isEmpty(q):
    Check if the Deque is empty and return a boolean value

isSize(q):
    Return the size of the Deque

insertFront(q, element):
    Create a new QNode with the given element
    Adjust pointers to insert the node at the front
    Increment the size of the Deque

insertRear(q, element):
    Create a new QNode with the given element
    Adjust pointers to insert the node at the rear
    Increment the size of the Deque

deleteFront(q):
    Remove the front node from the Deque
    Adjust pointers and size

deleteRear(q):
    Remove the rear node from the Deque
    Adjust pointers and size

peekFront(q):
    Return the element at the front of the Deque without removing it

peekRear(q):
    Return the element at the rear of the Deque without removing it

printDqueue(q):
    Traverse the Deque and print the elements

Main:
    Initialize a new Deque
    Insert elements at both ends of the Deque
    Print the Deque elements and size
    Get and print the front and rear elements
    Delete elements from both ends of the Deque
    Print the updated Deque elements and size
    Get and print the front and rear elements

Algorithm Explanation

  1. Initialize a new Deque using the newDeque function.
  2. Insert elements at the front and rear of the Deque using the insertFront and insertRear functions.
  3. Print the Deque elements and size using the printDqueue and isSize functions.
  4. Use the peekFront and peekRear functions to get and print the front and rear elements of the Deque.
  5. Use the deleteFront and deleteRear functions to remove elements from the front and rear of the Deque.
  6. Print the updated Deque elements and size.

Code Solution

/*
    C Program 
    Deque implementation using doubly linked list
*/
#include <stdio.h>
#include <stdlib.h>

// Queue Node
struct QNode
{
	int element;
	struct QNode *next;
	struct QNode *prev;
};
// Structure of Deque
struct Deque
{
	struct QNode *front;
	struct QNode *rear;
	int size;
};
// Returns a new queue 
struct Deque *newDeque()
{
	struct Deque *q = (struct Deque *) malloc(sizeof(struct Deque));
	if (q == NULL)
	{
		printf("\n Memory overflow , When creating a new Deque");
	}
	else
	{
		// Set initial value
		q->front = NULL;
		q->rear = NULL;
		q->size = 0;
	}
	return q;
}
int isEmpty(struct Deque *q)
{
	if (q->size == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
// Returns the number of elements in queue
int isSize(struct Deque *q)
{
	return q->size;
}
// Add node at beginning of queue
void insertFront(struct Deque *q, int element)
{
	// Make a new Queue node
	struct QNode *node = (struct QNode *) malloc(sizeof(struct QNode));
	if (node != NULL)
	{
		// Set node values
		node->element = element;
		node->next = q->front;
		node->prev = NULL;
		if (q->front == NULL)
		{
			//  When inserting a first node of queue
			q->front = node;
			q->rear = node;
		}
		else
		{
			// Add node at beginning position
			q->front->prev = node;
			q->front = node;
		}
		q->size++;
	}
	else
	{
		printf("\n Memory Overflow, when creating a new Queue Node\n");
	}
}
// Add node at end of queue
void insertRear(struct Deque *q, int element)
{
	// Make a new Queue node
	struct QNode *node = (struct QNode *) malloc(sizeof(struct QNode));
	if (node != NULL)
	{
		// Set node values
		node->element = element;
		node->next = NULL;
		node->prev = NULL;
		if (q->front == NULL)
		{
			//  When inserting a first node of queue
			q->front = node;
			q->rear = node;
		}
		else
		{
			// Add node at the end
			q->rear->next = node;
			node->prev = q->rear;
			q->rear = node;
		}
		q->size++;
	}
	else
	{
		printf("\n Memory Overflow, when creating a new Queue Node\n");
	}
}
// Delete first node 
void deleteFront(struct Deque *q)
{
	if (isEmpty(q) == 1)
	{
		return;
	}
	struct QNode *temp = q->front;
	q->front = temp->next;
	if (q->front == NULL)
	{
		q->rear = NULL;
	}
	else
	{
		q->front->prev = NULL;
	}
	q->size--;
	free(temp);
}
// Delete last node 
void deleteRear(struct Deque *q)
{
	if (isEmpty(q) == 1)
	{
		return;
	}
	struct QNode *temp = q->rear;
	q->rear = temp->prev;
	if (q->rear == NULL)
	{
		q->front = NULL;
	}
	else
	{
		q->rear->next = NULL;
	}
	q->size--;
	free(temp);
}
// Returns the first element
int peekFront(struct Deque *q)
{
	if (isEmpty(q) == 1)
	{
		printf("\n Empty Deque \n");
		return -1;
	}
	return q->front->element;
}
// Returns the last element
int peekRear(struct Deque *q)
{
	if (isEmpty(q) == 1)
	{
		printf("\n Empty Deque \n");
		return -1;
	}
	return q->rear->element;
}
// Print the elements of Deque  
void printDqueue(struct Deque *q)
{
	struct QNode *node = q->front;
	printf("\n Deque Element \n");
	// Display node of from front to rear
	while (node != NULL)
	{
		printf(" %d", node->element);
		node = node->next;
	}
	printf("\n");
}
int main(int argc, char
	const *argv[])
{
	struct Deque *q = newDeque();
	// Add Deque element
	// Add node at beginning position
	insertFront(q, 1);
	insertFront(q, 2);
	// Add node at last position
	insertRear(q, 3);
	insertRear(q, 4);
	// Add node at beginning position
	insertFront(q, 5);
	insertFront(q, 6);
	// Print inserted node
	printDqueue(q);
	printf(" Size : %d", isSize(q));
	// Get first and last element
	printf("\n Front Node : %d", peekFront(q));
	printf("\n Rear Node  : %d", peekRear(q));
	// Remove queue element
	deleteFront(q);
	deleteRear(q);
	// After delete element
	printf(" Size : %d", isSize(q));
	printDqueue(q);
	// Get first and last element
	printf(" Front Node : %d", peekFront(q));
	printf("\n Rear Node  : %d", peekRear(q));
	return 0;
}

Output

 Deque Element
 6 5 2 1 3 4
 Size : 6
 Front Node : 6
 Rear Node  : 4 Size : 4
 Deque Element
 5 2 1 3
 Front Node : 5
 Rear Node  : 3
/*
    Java Program 
    Deque implementation using doubly linked list
*/
// Queue Node
class QNode
{
    public int element;
    public QNode next;
    public QNode prev;
    public QNode(int element)
    {
        this.element = element;
        this.next = null;
        this.prev = null;
    }
}
// Implement Deque
public class Deque
{
    public QNode front;
    public QNode rear;
    public int size;
    public Deque()
    {
        this.front = null;
        this.rear = null;
        this.size = 0;
    }
    public boolean isEmpty()
    {
        if (this.size == 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    // Returns the number of elements in queue
    public int isSize()
    {
        return this.size;
    }
    // Add node at beginning of queue
    public void insertFront(int element)
    {
        // Make a new Queue node
        QNode node = new QNode(element);
        node.next =  this.front;
        if (this.front == null)
        {
            //  When inserting a first node of queue
            this.front = node;
            this.rear = node;
        }
        else
        {
            // Add node at beginning position
            this.front.prev = node;
            this.front = node;
        }
        this.size++;
    }
    // Add node at end of queue
    public void insertRear(int element)
    {
        // Make a new Queue node
        QNode node = new QNode(element);
        if (this.front == null)
        {
            //  When inserting a first node of queue
            this.front = node;
            this.rear = node;
        }
        else
        {
            // Add node at the end
            this.rear.next = node;
            node.prev = this.rear;
            this.rear = node;
        }
        this.size++;
    }
    // Delete first node 
    public void deleteFront()
    {
        if (this.isEmpty() == true)
        {
            return;
        }
        QNode temp = this.front;
        this.front = temp.next;
        if (this.front == null)
        {
            this.rear = null;
        }
        else
        {
            this.front.prev = null;
        }
        this.size--;
        temp = null;
    }
    // Delete last node 
    public void deleteRear()
    {
        if (this.isEmpty() == true)
        {
            return;
        }
        QNode temp = this.rear;
        this.rear = temp.prev;
        if (this.rear == null)
        {
            this.front = null;
        }
        else
        {
            this.rear.next = null;
        }
        this.size--;
        temp = null;
    }
    // Returns the first element
    public int peekFront()
    {
        if (this.isEmpty() == true)
        {
            System.out.print("\n Empty Deque \n");
            return -1;
        }
        return this.front.element;
    }
    // Returns the last element
    public int peekRear()
    {
        if (this.isEmpty() == true)
        {
            System.out.print("\n Empty Deque \n");
            return -1;
        }
        return this.rear.element;
    }
    // Print the elements of Deque  
    public void printDqueue()
    {
        QNode node = this.front;
        System.out.print("\n Deque Element \n");
        // Display node of from front to rear
        while (node != null)
        {
            System.out.print(" " + node.element);
            node = node.next;
        }
        System.out.print("\n");
    }
    public static void main(String[] args)
    {
        Deque q = new Deque();
        // Add Deque element
        // Add node at beginning position
        q.insertFront(1);
        q.insertFront(2);
        // Add node at last position
        q.insertRear(3);
        q.insertRear(4);
        // Add node at beginning position
        q.insertFront(5);
        q.insertFront(6);
        // Print inserted node
        q.printDqueue();
        System.out.print(" Size : " + q.isSize());
        // Get first and last element
        System.out.print("\n Front Node : " + q.peekFront());
        System.out.print("\n Rear Node : " + q.peekRear());
        // Remove queue element
        q.deleteFront();
        q.deleteRear();
        // After delete element
        System.out.print("\n Size : " + q.isSize());
        q.printDqueue();
        // Get first and last element
        System.out.print(" Front Node : " + q.peekFront());
        System.out.print("\n Rear Node : " + q.peekRear());
    }
}

Output

 Deque Element
 6 5 2 1 3 4
 Size : 6
 Front Node : 6
 Rear Node : 4
 Size : 4
 Deque Element
 5 2 1 3
 Front Node : 5
 Rear Node : 3
// Include header file
#include <iostream>
using namespace std;
/*
    C++ Program 
    Deque implementation using doubly linked list
*/
// Queue Node
class QNode
{
	public: int element;
	QNode *next;
	QNode *prev;
	QNode(int element)
	{
		this->element = element;
		this->next = NULL;
		this->prev = NULL;
	}
};
// Implement Deque
class Deque
{
	public: QNode *front;
	QNode *rear;
	int size;
	Deque()
	{
		this->front = NULL;
		this->rear = NULL;
		this->size = 0;
	}
	bool isEmpty()
	{
		if (this->size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Returns the number of elements in queue
	int isSize()
	{
		return this->size;
	}
	// Add node at beginning of queue
	void insertFront(int element)
	{
		// Make a new Queue node
		QNode *node = new QNode(element);
		node->next = this->front;
		if (this->front == NULL)
		{
			//  When inserting a first node of queue
			this->front = node;
			this->rear = node;
		}
		else
		{
			// Add node at beginning position
			this->front->prev = node;
			this->front = node;
		}
		this->size++;
	}
	// Add node at end of queue
	void insertRear(int element)
	{
		// Make a new Queue node
		QNode *node = new QNode(element);
		if (this->front == NULL)
		{
			//  When inserting a first node of queue
			this->front = node;
			this->rear = node;
		}
		else
		{
			// Add node at the end
			this->rear->next = node;
			node->prev = this->rear;
			this->rear = node;
		}
		this->size++;
	}
	// Delete first node
	void deleteFront()
	{
		if (this->isEmpty() == true)
		{
			return;
		}
		QNode *temp = this->front;
		this->front = temp->next;
		if (this->front == NULL)
		{
			this->rear = NULL;
		}
		else
		{
			this->front->prev = NULL;
		}
		this->size--;
		temp = NULL;
	}
	// Delete last node
	void deleteRear()
	{
		if (this->isEmpty() == true)
		{
			return;
		}
		QNode *temp = this->rear;
		this->rear = temp->prev;
		if (this->rear == NULL)
		{
			this->front = NULL;
		}
		else
		{
			this->rear->next = NULL;
		}
		this->size--;
		temp = NULL;
	}
	// Returns the first element
	int peekFront()
	{
		if (this->isEmpty() == true)
		{
			cout << "\n Empty Deque \n";
			return -1;
		}
		return this->front->element;
	}
	// Returns the last element
	int peekRear()
	{
		if (this->isEmpty() == true)
		{
			cout << "\n Empty Deque \n";
			return -1;
		}
		return this->rear->element;
	}
	// Print the elements of Deque
	void printDqueue()
	{
		QNode *node = this->front;
		cout << "\n Deque Element \n";
		// Display node of from front to rear
		while (node != NULL)
		{
			cout << " " << node->element;
			node = node->next;
		}
		cout << "\n";
	}
};
int main()
{
	Deque q = Deque();
	// Add Deque element
	// Add node at beginning position
	q.insertFront(1);
	q.insertFront(2);
	// Add node at last position
	q.insertRear(3);
	q.insertRear(4);
	// Add node at beginning position
	q.insertFront(5);
	q.insertFront(6);
	// Print inserted node
	q.printDqueue();
	cout << " Size : " << q.isSize();
	// Get first and last element
	cout << "\n Front Node : " << q.peekFront();
	cout << "\n Rear Node : " << q.peekRear();
	// Remove queue element
	q.deleteFront();
	q.deleteRear();
	// After delete element
	cout << "\n Size : " << q.isSize();
	q.printDqueue();
	// Get first and last element
	cout << " Front Node : " << q.peekFront();
	cout << "\n Rear Node : " << q.peekRear();
	return 0;
}

Output

 Deque Element
 6 5 2 1 3 4
 Size : 6
 Front Node : 6
 Rear Node : 4
 Size : 4
 Deque Element
 5 2 1 3
 Front Node : 5
 Rear Node : 3
// Include namespace system
using System;
/*
    C# Program 
    Deque implementation using doubly linked list
*/
// Queue Node
public class QNode
{
	public int element;
	public QNode next;
	public QNode prev;
	public QNode(int element)
	{
		this.element = element;
		this.next = null;
		this.prev = null;
	}
}
// Implement Deque
public class Deque
{
	public QNode front;
	public QNode rear;
	public int size;
	public Deque()
	{
		this.front = null;
		this.rear = null;
		this.size = 0;
	}
	public Boolean isEmpty()
	{
		if (this.size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Returns the number of elements in queue
	public int isSize()
	{
		return this.size;
	}
	// Add node at beginning of queue
	public void insertFront(int element)
	{
		// Make a new Queue node
		QNode node = new QNode(element);
		node.next = this.front;
		if (this.front == null)
		{
			//  When inserting a first node of queue
			this.front = node;
			this.rear = node;
		}
		else
		{
			// Add node at beginning position
			this.front.prev = node;
			this.front = node;
		}
		this.size++;
	}
	// Add node at end of queue
	public void insertRear(int element)
	{
		// Make a new Queue node
		QNode node = new QNode(element);
		if (this.front == null)
		{
			//  When inserting a first node of queue
			this.front = node;
			this.rear = node;
		}
		else
		{
			// Add node at the end
			this.rear.next = node;
			node.prev = this.rear;
			this.rear = node;
		}
		this.size++;
	}
	// Delete first node
	public void deleteFront()
	{
		if (this.isEmpty() == true)
		{
			return;
		}
		QNode temp = this.front;
		this.front = temp.next;
		if (this.front == null)
		{
			this.rear = null;
		}
		else
		{
			this.front.prev = null;
		}
		this.size--;
		temp = null;
	}
	// Delete last node
	public void deleteRear()
	{
		if (this.isEmpty() == true)
		{
			return;
		}
		QNode temp = this.rear;
		this.rear = temp.prev;
		if (this.rear == null)
		{
			this.front = null;
		}
		else
		{
			this.rear.next = null;
		}
		this.size--;
		temp = null;
	}
	// Returns the first element
	public int peekFront()
	{
		if (this.isEmpty() == true)
		{
			Console.Write("\n Empty Deque \n");
			return -1;
		}
		return this.front.element;
	}
	// Returns the last element
	public int peekRear()
	{
		if (this.isEmpty() == true)
		{
			Console.Write("\n Empty Deque \n");
			return -1;
		}
		return this.rear.element;
	}
	// Print the elements of Deque
	public void printDqueue()
	{
		QNode node = this.front;
		Console.Write("\n Deque Element \n");
		// Display node of from front to rear
		while (node != null)
		{
			Console.Write(" " + node.element);
			node = node.next;
		}
		Console.Write("\n");
	}
	public static void Main(String[] args)
	{
		Deque q = new Deque();
		// Add Deque element
		// Add node at beginning position
		q.insertFront(1);
		q.insertFront(2);
		// Add node at last position
		q.insertRear(3);
		q.insertRear(4);
		// Add node at beginning position
		q.insertFront(5);
		q.insertFront(6);
		// Print inserted node
		q.printDqueue();
		Console.Write(" Size : " + q.isSize());
		// Get first and last element
		Console.Write("\n Front Node : " + q.peekFront());
		Console.Write("\n Rear Node : " + q.peekRear());
		// Remove queue element
		q.deleteFront();
		q.deleteRear();
		// After delete element
		Console.Write("\n Size : " + q.isSize());
		q.printDqueue();
		// Get first and last element
		Console.Write(" Front Node : " + q.peekFront());
		Console.Write("\n Rear Node : " + q.peekRear());
	}
}

Output

 Deque Element
 6 5 2 1 3 4
 Size : 6
 Front Node : 6
 Rear Node : 4
 Size : 4
 Deque Element
 5 2 1 3
 Front Node : 5
 Rear Node : 3
<?php
/*
    Php Program 
    Deque implementation using doubly linked list
*/
// Queue Node
class QNode
{
	public $element;
	public $next;
	public $prev;

	function __construct($element)
	{
		$this->element = $element;
		$this->next = null;
		$this->prev = null;
	}
}
// Implement Deque
class Deque
{
	public $front;
	public $rear;
	public $size;

	function __construct()
	{
		$this->front = null;
		$this->rear = null;
		$this->size = 0;
	}
	public	function isEmpty()
	{
		if ($this->size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Returns the number of elements in queue
	public	function isSize()
	{
		return $this->size;
	}
	// Add node at beginning of queue
	public	function insertFront($element)
	{
		// Make a new Queue node
		$node = new QNode($element);
		$node->next = $this->front;
		if ($this->front == null)
		{
			//  When inserting a first node of queue
			$this->front = $node;
			$this->rear = $node;
		}
		else
		{
			// Add node at beginning position
			$this->front->prev = $node;
			$this->front = $node;
		}
		$this->size++;
	}
	// Add node at end of queue
	public	function insertRear($element)
	{
		// Make a new Queue node
		$node = new QNode($element);
		if ($this->front == null)
		{
			//  When inserting a first node of queue
			$this->front = $node;
			$this->rear = $node;
		}
		else
		{
			// Add node at the end
			$this->rear->next = $node;
			$node->prev = $this->rear;
			$this->rear = $node;
		}
		$this->size++;
	}
	// Delete first node
	public	function deleteFront()
	{
		if ($this->isEmpty() == true)
		{
			return;
		}
		$temp = $this->front;
		$this->front = $temp->next;
		if ($this->front == null)
		{
			$this->rear = null;
		}
		else
		{
			$this->front->prev = null;
		}
		$this->size--;
		$temp = null;
	}
	// Delete last node
	public	function deleteRear()
	{
		if ($this->isEmpty() == true)
		{
			return;
		}
		$temp = $this->rear;
		$this->rear = $temp->prev;
		if ($this->rear == null)
		{
			$this->front = null;
		}
		else
		{
			$this->rear->next = null;
		}
		$this->size--;
		$temp = null;
	}
	// Returns the first element
	public	function peekFront()
	{
		if ($this->isEmpty() == true)
		{
			echo "\n Empty Deque \n";
			return -1;
		}
		return $this->front->element;
	}
	// Returns the last element
	public	function peekRear()
	{
		if ($this->isEmpty() == true)
		{
			echo "\n Empty Deque \n";
			return -1;
		}
		return $this->rear->element;
	}
	// Print the elements of Deque
	public	function printDqueue()
	{
		$node = $this->front;
		echo "\n Deque Element \n";
		// Display node of from front to rear
		while ($node != null)
		{
			echo " ". $node->element;
			$node = $node->next;
		}
		echo "\n";
	}
}

function main()
{
	$q = new Deque();
	// Add Deque element
	// Add node at beginning position
	$q->insertFront(1);
	$q->insertFront(2);
	// Add node at last position
	$q->insertRear(3);
	$q->insertRear(4);
	// Add node at beginning position
	$q->insertFront(5);
	$q->insertFront(6);
	// Print inserted node
	$q->printDqueue();
	echo " Size : ". $q->isSize();
	// Get first and last element
	echo "\n Front Node : ". $q->peekFront();
	echo "\n Rear Node : ". $q->peekRear();
	// Remove queue element
	$q->deleteFront();
	$q->deleteRear();
	// After delete element
	echo "\n Size : ". $q->isSize();
	$q->printDqueue();
	// Get first and last element
	echo " Front Node : ". $q->peekFront();
	echo "\n Rear Node : ". $q->peekRear();
}
main();

Output

 Deque Element
 6 5 2 1 3 4
 Size : 6
 Front Node : 6
 Rear Node : 4
 Size : 4
 Deque Element
 5 2 1 3
 Front Node : 5
 Rear Node : 3
/*
    Node Js Program 
    Deque implementation using doubly linked list
*/
// Queue Node
class QNode
{
	constructor(element)
	{
		this.element = element;
		this.next = null;
		this.prev = null;
	}
}
// Implement Deque
class Deque
{
	constructor()
	{
		this.front = null;
		this.rear = null;
		this.size = 0;
	}
	isEmpty()
	{
		if (this.size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Returns the number of elements in queue
	isSize()
	{
		return this.size;
	}
	// Add node at beginning of queue
	insertFront(element)
	{
		// Make a new Queue node
		var node = new QNode(element);
		node.next = this.front;
		if (this.front == null)
		{
			//  When inserting a first node of queue
			this.front = node;
			this.rear = node;
		}
		else
		{
			// Add node at beginning position
			this.front.prev = node;
			this.front = node;
		}
		this.size++;
	}
	// Add node at end of queue
	insertRear(element)
	{
		// Make a new Queue node
		var node = new QNode(element);
		if (this.front == null)
		{
			//  When inserting a first node of queue
			this.front = node;
			this.rear = node;
		}
		else
		{
			// Add node at the end
			this.rear.next = node;
			node.prev = this.rear;
			this.rear = node;
		}
		this.size++;
	}
	// Delete first node
	deleteFront()
	{
		if (this.isEmpty() == true)
		{
			return;
		}
		var temp = this.front;
		this.front = temp.next;
		if (this.front == null)
		{
			this.rear = null;
		}
		else
		{
			this.front.prev = null;
		}
		this.size--;
		temp = null;
	}
	// Delete last node
	deleteRear()
	{
		if (this.isEmpty() == true)
		{
			return;
		}
		var temp = this.rear;
		this.rear = temp.prev;
		if (this.rear == null)
		{
			this.front = null;
		}
		else
		{
			this.rear.next = null;
		}
		this.size--;
		temp = null;
	}
	// Returns the first element
	peekFront()
	{
		if (this.isEmpty() == true)
		{
			process.stdout.write("\n Empty Deque \n");
			return -1;
		}
		return this.front.element;
	}
	// Returns the last element
	peekRear()
	{
		if (this.isEmpty() == true)
		{
			process.stdout.write("\n Empty Deque \n");
			return -1;
		}
		return this.rear.element;
	}
	// Print the elements of Deque
	printDqueue()
	{
		var node = this.front;
		process.stdout.write("\n Deque Element \n");
		// Display node of from front to rear
		while (node != null)
		{
			process.stdout.write(" " + node.element);
			node = node.next;
		}
		process.stdout.write("\n");
	}
}

function main()
{
	var q = new Deque();
	// Add Deque element
	// Add node at beginning position
	q.insertFront(1);
	q.insertFront(2);
	// Add node at last position
	q.insertRear(3);
	q.insertRear(4);
	// Add node at beginning position
	q.insertFront(5);
	q.insertFront(6);
	// Print inserted node
	q.printDqueue();
	process.stdout.write(" Size : " + q.isSize());
	// Get first and last element
	process.stdout.write("\n Front Node : " + q.peekFront());
	process.stdout.write("\n Rear Node : " + q.peekRear());
	// Remove queue element
	q.deleteFront();
	q.deleteRear();
	// After delete element
	process.stdout.write("\n Size : " + q.isSize());
	q.printDqueue();
	// Get first and last element
	process.stdout.write(" Front Node : " + q.peekFront());
	process.stdout.write("\n Rear Node : " + q.peekRear());
}
main();

Output

 Deque Element
 6 5 2 1 3 4
 Size : 6
 Front Node : 6
 Rear Node : 4
 Size : 4
 Deque Element
 5 2 1 3
 Front Node : 5
 Rear Node : 3
#  Python 3 Program 
#  Deque implementation using doubly linked list

#  Queue Node
class QNode :
	
	def __init__(self, element) :
		self.element = element
		self.next = None
		self.prev = None
	

#  Implement Deque
class Deque :
	
	def __init__(self) :
		self.front = None
		self.rear = None
		self.size = 0
	
	def isEmpty(self) :
		if (self.size == 0) :
			return True
		else :
			return False
		
	
	#  Returns the number of elements in queue
	def isSize(self) :
		return self.size
	
	#  Add node at beginning of queue
	def insertFront(self, element) :
		#  Make a new Queue node
		node = QNode(element)
		node.next = self.front
		if (self.front == None) :
			#   When inserting a first node of queue
			self.front = node
			self.rear = node
		else :
			#  Add node at beginning position
			self.front.prev = node
			self.front = node
		
		self.size += 1
	
	#  Add node at end of queue
	def insertRear(self, element) :
		#  Make a new Queue node
		node = QNode(element)
		if (self.front == None) :
			#   When inserting a first node of queue
			self.front = node
			self.rear = node
		else :
			#  Add node at the end
			self.rear.next = node
			node.prev = self.rear
			self.rear = node
		
		self.size += 1
	
	#  Delete first node 
	def deleteFront(self) :
		if (self.isEmpty() == True) :
			return
		
		temp = self.front
		self.front = temp.next
		if (self.front == None) :
			self.rear = None
		else :
			self.front.prev = None
		
		self.size -= 1
		temp = None
	
	#  Delete last node 
	def deleteRear(self) :
		if (self.isEmpty() == True) :
			return
		
		temp = self.rear
		self.rear = temp.prev
		if (self.rear == None) :
			self.front = None
		else :
			self.rear.next = None
		
		self.size -= 1
		temp = None
	
	#  Returns the first element
	def peekFront(self) :
		if (self.isEmpty() == True) :
			print("\n Empty Deque ")
			return -1
		
		return self.front.element
	
	#  Returns the last element
	def peekRear(self) :
		if (self.isEmpty() == True) :
			print("\n Empty Deque ")
			return -1
		
		return self.rear.element
	
	#  Print the elements of Deque  
	def printDqueue(self) :
		node = self.front
		print("\n Deque Element ")
		#  Display node of from front to rear
		while (node != None) :
			print(" ", node.element, end = "")
			node = node.next
		
		print(end = "\n")
	

def main() :
	q = Deque()
	#  Add Deque element
	#  Add node at beginning position
	q.insertFront(1)
	q.insertFront(2)
	#  Add node at last position
	q.insertRear(3)
	q.insertRear(4)
	#  Add node at beginning position
	q.insertFront(5)
	q.insertFront(6)
	#  Print inserted node
	q.printDqueue()
	print(" Size : ", q.isSize(), end = "")
	#  Get first and last element
	print("\n Front Node : ", q.peekFront(), end = "")
	print("\n Rear Node : ", q.peekRear(), end = "")
	#  Remove queue element
	q.deleteFront()
	q.deleteRear()
	#  After delete element
	print("\n Size : ", q.isSize(), end = "")
	q.printDqueue()
	#  Get first and last element
	print(" Front Node : ", q.peekFront(), end = "")
	print("\n Rear Node : ", q.peekRear(), end = "")

if __name__ == "__main__": main()

Output

 Deque Element
  6  5  2  1  3  4
 Size :  6
 Front Node :  6
 Rear Node :  4
 Size :  4
 Deque Element
  5  2  1  3
 Front Node :  5
 Rear Node :  3
#  Ruby Program 
#  Deque implementation using doubly linked list

#  Queue Node
class QNode  
	# Define the accessor and reader of class QNode  
	attr_reader :element, :next, :prev
	attr_accessor :element, :next, :prev
 
	
	def initialize(element) 
		self.element = element
		self.next = nil
		self.prev = nil
	end

end

#  Implement Deque
class Deque  
	# Define the accessor and reader of class Deque  
	attr_reader :front, :rear, :size
	attr_accessor :front, :rear, :size
 
	
	def initialize() 
		self.front = nil
		self.rear = nil
		self.size = 0
	end

	def isEmpty() 
		if (self.size == 0) 
			return true
		else 
			return false
		end

	end

	#  Returns the number of elements in queue
	def isSize() 
		return self.size
	end

	#  Add node at beginning of queue
	def insertFront(element) 
		#  Make a new Queue node
		node = QNode.new(element)
		node.next = self.front
		if (self.front == nil) 
			#   When inserting a first node of queue
			self.front = node
			self.rear = node
		else 
			#  Add node at beginning position
			self.front.prev = node
			self.front = node
		end

		self.size += 1
	end

	#  Add node at end of queue
	def insertRear(element) 
		#  Make a new Queue node
		node = QNode.new(element)
		if (self.front == nil) 
			#   When inserting a first node of queue
			self.front = node
			self.rear = node
		else 
			#  Add node at the end
			self.rear.next = node
			node.prev = self.rear
			self.rear = node
		end

		self.size += 1
	end

	#  Delete first node 
	def deleteFront() 
		if (self.isEmpty() == true) 
			return
		end

		temp = self.front
		self.front = temp.next
		if (self.front == nil) 
			self.rear = nil
		else 
			self.front.prev = nil
		end

		self.size -= 1
		temp = nil
	end

	#  Delete last node 
	def deleteRear() 
		if (self.isEmpty() == true) 
			return
		end

		temp = self.rear
		self.rear = temp.prev
		if (self.rear == nil) 
			self.front = nil
		else 
			self.rear.next = nil
		end

		self.size -= 1
		temp = nil
	end

	#  Returns the first element
	def peekFront() 
		if (self.isEmpty() == true) 
			print("\n Empty Deque \n")
			return -1
		end

		return self.front.element
	end

	#  Returns the last element
	def peekRear() 
		if (self.isEmpty() == true) 
			print("\n Empty Deque \n")
			return -1
		end

		return self.rear.element
	end

	#  Print the elements of Deque  
	def printDqueue() 
		node = self.front
		print("\n Deque Element \n")
		#  Display node of from front to rear
		while (node != nil) 
			print(" ", node.element)
			node = node.next
		end

		print("\n")
	end

end

def main() 
	q = Deque.new()
	#  Add Deque element
	#  Add node at beginning position
	q.insertFront(1)
	q.insertFront(2)
	#  Add node at last position
	q.insertRear(3)
	q.insertRear(4)
	#  Add node at beginning position
	q.insertFront(5)
	q.insertFront(6)
	#  Print inserted node
	q.printDqueue()
	print(" Size : ", q.isSize())
	#  Get first and last element
	print("\n Front Node : ", q.peekFront())
	print("\n Rear Node : ", q.peekRear())
	#  Remove queue element
	q.deleteFront()
	q.deleteRear()
	#  After delete element
	print("\n Size : ", q.isSize())
	q.printDqueue()
	#  Get first and last element
	print(" Front Node : ", q.peekFront())
	print("\n Rear Node : ", q.peekRear())
end

main()

Output

 Deque Element 
 6 5 2 1 3 4
 Size : 6
 Front Node : 6
 Rear Node : 4
 Size : 4
 Deque Element 
 5 2 1 3
 Front Node : 5
 Rear Node : 3
/*
    Scala Program 
    Deque implementation using doubly linked list
*/
// Queue Node
class QNode(var element: Int , var next: QNode , var prev: QNode)
{
	def this(element: Int)
	{
		this(element, null, null);
	}
}
// Implement Deque
class Deque(var front: QNode , var rear: QNode , var size: Int)
{
	def this()
	{
		this(null, null, 0);
	}
	def isEmpty(): Boolean = {
		if (this.size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Returns the number of elements in queue
	def isSize(): Int = {
		return this.size;
	}
	// Add node at beginning of queue
	def insertFront(element: Int): Unit = {
		// Make a new Queue node
		var node: QNode = new QNode(element);
		node.next = this.front;
		if (this.front == null)
		{
			//  When inserting a first node of queue
			this.front = node;
			this.rear = node;
		}
		else
		{
			// Add node at beginning position
			this.front.prev = node;
			this.front = node;
		}
		this.size += 1;
	}
	// Add node at end of queue
	def insertRear(element: Int): Unit = {
		// Make a new Queue node
		var node: QNode = new QNode(element);
		if (this.front == null)
		{
			//  When inserting a first node of queue
			this.front = node;
			this.rear = node;
		}
		else
		{
			// Add node at the end
			this.rear.next = node;
			node.prev = this.rear;
			this.rear = node;
		}
		this.size += 1;
	}
	// Delete first node
	def deleteFront(): Unit = {
		if (this.isEmpty() == true)
		{
			return;
		}
		var temp: QNode = this.front;
		this.front = temp.next;
		if (this.front == null)
		{
			this.rear = null;
		}
		else
		{
			this.front.prev = null;
		}
		this.size -= 1;
		temp = null;
	}
	// Delete last node
	def deleteRear(): Unit = {
		if (this.isEmpty() == true)
		{
			return;
		}
		var temp: QNode = this.rear;
		this.rear = temp.prev;
		if (this.rear == null)
		{
			this.front = null;
		}
		else
		{
			this.rear.next = null;
		}
		this.size -= 1;
		temp = null;
	}
	// Returns the first element
	def peekFront(): Int = {
		if (this.isEmpty() == true)
		{
			print("\n Empty Deque \n");
			return -1;
		}
		return this.front.element;
	}
	// Returns the last element
	def peekRear(): Int = {
		if (this.isEmpty() == true)
		{
			print("\n Empty Deque \n");
			return -1;
		}
		return this.rear.element;
	}
	// Print the elements of Deque
	def printDqueue(): Unit = {
		var node: QNode = this.front;
		print("\n Deque Element \n");
		// Display node of from front to rear
		while (node != null)
		{
			print(" " + node.element);
			node = node.next;
		}
		print("\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var q: Deque = new Deque();
		// Add Deque element
		// Add node at beginning position
		q.insertFront(1);
		q.insertFront(2);
		// Add node at last position
		q.insertRear(3);
		q.insertRear(4);
		// Add node at beginning position
		q.insertFront(5);
		q.insertFront(6);
		// Print inserted node
		q.printDqueue();
		print(" Size : " + q.isSize());
		// Get first and last element
		print("\n Front Node : " + q.peekFront());
		print("\n Rear Node : " + q.peekRear());
		// Remove queue element
		q.deleteFront();
		q.deleteRear();
		// After delete element
		print("\n Size : " + q.isSize());
		q.printDqueue();
		// Get first and last element
		print(" Front Node : " + q.peekFront());
		print("\n Rear Node : " + q.peekRear());
	}
}

Output

 Deque Element
 6 5 2 1 3 4
 Size : 6
 Front Node : 6
 Rear Node : 4
 Size : 4
 Deque Element
 5 2 1 3
 Front Node : 5
 Rear Node : 3
/*
    Swift 4 Program 
    Deque implementation using doubly linked list
*/
// Queue Node
class QNode
{
	var element: Int;
	var next: QNode? ;
	var prev: QNode? ;
	init(_ element: Int)
	{
		self.element = element;
		self.next = nil;
		self.prev = nil;
	}
}
// Implement Deque
class Deque
{
	var front: QNode? ;
	var rear: QNode? ;
	var size: Int;
	init()
	{
		self.front = nil;
		self.rear = nil;
		self.size = 0;
	}
	func isEmpty()->Bool
	{
		if (self.size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Returns the number of elements in queue
	func isSize()->Int
	{
		return self.size;
	}
	// Add node at beginning of queue
	func insertFront(_ element: Int)
	{
		// Make a new Queue node
		let node: QNode? = QNode(element);
		node!.next = self.front;
		if (self.front == nil)
		{
			//  When inserting a first node of queue
			self.front = node;
			self.rear = node;
		}
		else
		{
			// Add node at beginning position
			self.front!.prev = node;
			self.front = node;
		}
		self.size += 1;
	}
	// Add node at end of queue
	func insertRear(_ element: Int)
	{
		// Make a new Queue node
		let node: QNode? = QNode(element);
		if (self.front == nil)
		{
			//  When inserting a first node of queue
			self.front = node;
			self.rear = node;
		}
		else
		{
			// Add node at the end
			self.rear!.next = node;
			node!.prev = self.rear;
			self.rear = node;
		}
		self.size += 1;
	}
	// Delete first node
	func deleteFront()
	{
		if (self.isEmpty() == true)
		{
			return;
		}
		var temp: QNode? = self.front;
		self.front = temp!.next;
		if (self.front == nil)
		{
			self.rear = nil;
		}
		else
		{
			self.front!.prev = nil;
		}
		self.size -= 1;
		temp = nil;
	}
	// Delete last node
	func deleteRear()
	{
		if (self.isEmpty() == true)
		{
			return;
		}
		var temp: QNode? = self.rear;
		self.rear = temp!.prev;
		if (self.rear == nil)
		{
			self.front = nil;
		}
		else
		{
			self.rear!.next = nil;
		}
		self.size -= 1;
		temp = nil;
	}
	// Returns the first element
	func peekFront()->Int
	{
		if (self.isEmpty() == true)
		{
			print("\n Empty Deque ");
			return -1;
		}
		return self.front!.element;
	}
	// Returns the last element
	func peekRear()->Int
	{
		if (self.isEmpty() == true)
		{
			print("\n Empty Deque ");
			return -1;
		}
		return self.rear!.element;
	}
	// Print the elements of Deque
	func printDqueue()
	{
		var node: QNode? = self.front;
		print("\n Deque Element ");
		// Display node of from front to rear
		while (node  != nil)
		{
			print(" ", node!.element, terminator: "");
			node = node!.next;
		}
		print(terminator: "\n");
	}
}
func main()
{
	let q: Deque = Deque();
	// Add Deque element
	// Add node at beginning position
	q.insertFront(1);
	q.insertFront(2);
	// Add node at last position
	q.insertRear(3);
	q.insertRear(4);
	// Add node at beginning position
	q.insertFront(5);
	q.insertFront(6);
	// Print inserted node
	q.printDqueue();
	print(" Size : ", q.isSize(), terminator: "");
	// Get first and last element
	print("\n Front Node : ", q.peekFront(), terminator: "");
	print("\n Rear Node : ", q.peekRear(), terminator: "");
	// Remove queue element
	q.deleteFront();
	q.deleteRear();
	// After delete element
	print("\n Size : ", q.isSize(), terminator: "");
	q.printDqueue();
	// Get first and last element
	print(" Front Node : ", q.peekFront(), terminator: "");
	print("\n Rear Node : ", q.peekRear(), terminator: "");
}
main();

Output

 Deque Element
  6  5  2  1  3  4
 Size :  6
 Front Node :  6
 Rear Node :  4
 Size :  4
 Deque Element
  5  2  1  3
 Front Node :  5
 Rear Node :  3
/*
    Kotlin Program 
    Deque implementation using doubly linked list
*/
// Queue Node
class QNode
{
	var element: Int;
	var next: QNode ? ;
	var prev: QNode ? ;
	constructor(element: Int)
	{
		this.element = element;
		this.next = null;
		this.prev = null;
	}
}
// Implement Deque
class Deque
{
	var front: QNode ? ;
	var rear: QNode ? ;
	var size: Int;
	constructor()
	{
		this.front = null;
		this.rear = null;
		this.size = 0;
	}
	fun isEmpty(): Boolean
	{
		if (this.size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Returns the number of elements in queue
	fun isSize(): Int
	{
		return this.size;
	}
	// Add node at beginning of queue
	fun insertFront(element: Int): Unit
	{
		// Make a new Queue node
		var node: QNode ? = QNode(element);
		node?.next = this.front;
		if (this.front == null)
		{
			//  When inserting a first node of queue
			this.front = node;
			this.rear = node;
		}
		else
		{
			// Add node at beginning position
			this.front?.prev = node;
			this.front = node;
		}
		this.size += 1;
	}
	// Add node at end of queue
	fun insertRear(element: Int): Unit
	{
		// Make a new Queue node
		var node: QNode ? = QNode(element);
		if (this.front == null)
		{
			//  When inserting a first node of queue
			this.front = node;
			this.rear = node;
		}
		else
		{
			// Add node at the end
			this.rear?.next = node;
			node?.prev = this.rear;
			this.rear = node;
		}
		this.size += 1;
	}
	// Delete first node
	fun deleteFront(): Unit
	{
		if (this.isEmpty() == true)
		{
			return;
		}
		var temp: QNode ? = this.front;
		this.front = temp?.next;
		if (this.front == null)
		{
			this.rear = null;
		}
		else
		{
			this.front?.prev = null;
		}
		this.size -= 1;
		
	}
	// Delete last node
	fun deleteRear(): Unit
	{
		if (this.isEmpty() == true)
		{
			return;
		}
		var temp: QNode ? = this.rear;
		this.rear = temp?.prev;
		if (this.rear == null)
		{
			this.front = null;
		}
		else
		{
			this.rear?.next = null;
		}
		this.size -= 1;
	
	}
	// Returns the first element
	fun peekFront(): Int
	{
		if (this.isEmpty() == true)
		{
			print("\n Empty Deque \n");
			return -1;
		}
		return this.front!!.element;
	}
	// Returns the last element
	fun peekRear(): Int
	{
		if (this.isEmpty() == true)
		{
			print("\n Empty Deque \n");
			return -1;
		}
		return this.rear!!.element;
	}
	// Print the elements of Deque
	fun printDqueue(): Unit
	{
		var node: QNode ? = this.front;
		print("\n Deque Element \n");
		// Display node of from front to rear
		while (node != null)
		{
			print(" " + node.element);
			node = node.next;
		}
		print("\n");
	}
}
fun main(args: Array < String > ): Unit
{
	var q: Deque = Deque();
	// Add Deque element
	// Add node at beginning position
	q.insertFront(1);
	q.insertFront(2);
	// Add node at last position
	q.insertRear(3);
	q.insertRear(4);
	// Add node at beginning position
	q.insertFront(5);
	q.insertFront(6);
	// Print inserted node
	q.printDqueue();
	print(" Size : " + q.isSize());
	// Get first and last element
	print("\n Front Node : " + q.peekFront());
	print("\n Rear Node : " + q.peekRear());
	// Remove queue element
	q.deleteFront();
	q.deleteRear();
	// After delete element
	print("\n Size : " + q.isSize());
	q.printDqueue();
	// Get first and last element
	print(" Front Node : " + q.peekFront());
	print("\n Rear Node : " + q.peekRear());
}

Output

 Deque Element
 6 5 2 1 3 4
 Size : 6
 Front Node : 6
 Rear Node : 4
 Size : 4
 Deque Element
 5 2 1 3
 Front Node : 5
 Rear Node : 3

Resultant Output Explanation

The elements are inserted at the front and rear of the Deque, and the elements and size are printed. The front and rear elements are obtained and printed. After that, elements are deleted from both ends of the Deque, and the updated elements and size are printed again. The front and rear elements are once again obtained and printed.

Time Complexity

  1. Insertion (Front/Rear): O(1)
  2. Deletion (Front/Rear): O(1)
  3. Peek: O(1)
  4. IsEmpty: O(1)
  5. IsSize: O(1)

All operations in this Deque implementation have constant time complexity, making it efficient for real-world applications. This implementation provides a foundation for efficiently handling data using a Deque structure.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment