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 Queue 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-**