Deque Implementation in Java Using Doubly Linked List

In this post we’ll see an implementation of Deque in Java using Doubly Linked list.

Deque data structure

A Deque is a generalized queue structure that permits insertion and removal of elements at both ends where as in queue element can only be added at one end and removed from the other end.

Following image shows an implementation of Deque as doubly linked list with head and tail references.

Operations in a Deque

Mainly following operations are implemented for a Deque-

insertFirst- To insert an element at the beginning of a deque.
insertLast- To insert element at the last.
removeFirst- To remove item from the head of the queue.
removeLast- To remove item from the tail of the queue.
getFirst()- Read value from the front of the queue.
getLast()- Read last value from the queue.

For more information on these methods implementations refer Doubly Linked List Implementation Java Program.

Java program for Deque using doubly linked list

For representing nodes of the doubly linked list a separate class is used which apart from the data also has two references for storing next and previous references to itself.

class Node{
 //data
 int i;
 // next node in the list
 Node next;
 // previous node in the list
 Node prev;
}

There are also two references head and tail of type Node in the implementation class which are used to point to the first node of the Linked list (front of the queue) and the last node of the Linked list (rear of the queue) respectively.

public class LinkedListDeque {
 private Node head;
 private Node tail;
 
 static class Node{
  //data
  int i;
  // next node in the list
  Node next;
  // previous node in the list
  Node prev;
  Node(int i){
   this.i = i;
  }
  public void displayData(){
   System.out.print(i + " ");
  }
 }
 // constructor
 public LinkedListDeque(){
  this.head = null;
  this.tail = null;
 }
 
 public boolean isEmpty(){
  return head == null;
 }
 
 public void insertFirst(int i){
  //Create a new node
  Node newNode = new Node(i);
  // if first insertion tail should
  // also point to this node
  if(isEmpty()){
   tail = newNode;
  }else{
   head.prev = newNode;
  }
  newNode.next = head;
  head = newNode;
 }
 

 public void insertLast(int i){
  Node newNode = new Node(i);
  // if first insertion head should
  // also point to this node
  if(isEmpty()){
   head = newNode;
  }else{
   tail.next = newNode;
   newNode.prev = tail;
  }
  tail = newNode;
 }
 
 public Node removeFirst(){
  if(head == null){
   throw new RuntimeException("Deque is empty");
  }
  Node first = head;
  if(head.next == null){
   tail = null;
  }else{
   // previous of next node (new first) becomes null
   head.next.prev = null;
  }
  head = head.next;
  return first;
 }
 
 public Node removeLast(){
  if(tail == null){
   throw new RuntimeException("Deque is empty");
  }
  Node last = tail;
  if(head.next == null){
   head = null;
  }else{
   // next of previous node (new last) becomes null
   tail.prev.next = null;
  }
  tail = tail.prev;
  return last;
 }
 
 public int getFirst(){
  if(isEmpty()){
   throw new RuntimeException("Deque is empty");
  }
  return head.i;
 }
 
 public int getLast(){
  if(isEmpty()){
   throw new RuntimeException("Deque is empty");
  }
  return tail.i;
 }
 
 // Method for forward traversal
 public void displayForward(){
  Node current = head;
  while(current != null){
   current.displayData();
   current = current.next;
  }
  System.out.println("");
 }
 
 // Method to traverse and display all nodes
 public void displayBackward(){
  Node current = tail;
  while(current != null){
   current.displayData();
   current = current.prev;
  }
  System.out.println("");
 }

 public static void main(String[] args) {
  LinkedListDeque deque = new LinkedListDeque(); 
  //deque.getLast();
  deque.insertFirst(2);  
  deque.insertFirst(1);
  deque.insertLast(3);
  deque.insertLast(4);
  deque.displayForward();
  Node node = deque.removeFirst();
  System.out.println("Node with value "+ node.i + " deleted");
  deque.displayForward();
  System.out.println("First element in the deque " + deque.getFirst());
  System.out.println("Last element in the deque " + deque.getLast());
 }
}

Output

1 2 3 4 
Node with value 1 deleted
2 3 4 
First element in the deque 2
Last element in the deque 4

That's all for this topic Deque Implementation in Java Using Doubly Linked List. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Monday, May 30, 2022