Java ArrayDeque with Examples

This Java tutorial will discuss ArrayDeque class, and its main features with practical examples. We will also see the various methods present in this class and how we can use them either as a Stack or as a Queue in our code.

1. Introduction to ArrayDeque

A Queue is a linear data structure that stores elements in FIFO (First In, First Out) order. Each Queue has two ends: front and rear. New elements are added to the rear and removed from the front of the queue. Multiple sub-interfaces (like TransferQueue, BlockingQueue, etc.) and implementation classes (like LinkedList, PriorityQueue, etc.) use Queue Interface internally.

A Deque is a double-ended queue that allows adding or removing elements from both ends of the queue. It can be used as a Queue that follows FIFO(First In, First Out) order; or it can be used as a Stack that follows LIFO(Last In, First Out) order.

The ArrayDeque is the implementation class of Deque interface in Java; hence, ArrayDeque is a special kind of growable array that allows us to add or remove an element from both sides. It is also known as an ”Array Double Ended Queue or an ArrayDeck”.

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>

1.1. Constructors

We can create ArrayDeque object by using the following 2 constructors:

• ArrayDeque(): Used to create an empty ArrayDeque with default initial capacity of 16.
• ArrayDeque(Collection): Used to create an ArrayDeque having all the elements the same as that of the specified collection.
• ArrayDeque(int numofElements): Used to create an empty ArrayDeque with the specified initial capacity value.

Deque<String> deque = new ArrayDeque<String>();

Deque<String> deque = new ArrayDeque<String>(10);

Deque<String> deque = new ArrayDeque<>(Arrays.asList(new String("abc")));

1.2. Features

Let us cover some of the main features of ArrayDeque:

• We cannot insert Null elements in it, otherwise, it will throw NullPointerException.
• It is not Thread-safe and does not support concurrent access by multiple threads.
• It uses two pointers called head and tail. The head takes care of insertion and deletion from the front, and the tail takes care of insertion and deletion from the end.
•  It is faster than LinkedList and Stack.
• It has no capacity restrictions and grows as per the requirement.
• Iterator returned by it is fail-fast and can throw ConcurrentModificationException in case the collection modifies during iteration.

2. Working with ArrayDeque

The ArrayDeque class provides implementations for all the methods present in Queue and Deque Interfaces.

2.1. Adding Elements

The following methods offer to add new elements in the arraydeque.

• add(): inserts the specified element at the end of the array deque; if the deque is full, this method throws IllegalStateException.
• addFirst():  inserts the specified element at the beginning of the array deque; if the deque is full, this method throws IllegalStateException.
• addLast(): inserts the specified at the end of the array deque if the deque is full; this method throws IllegalStateException.
• offer(): inserts the specified element at the end of the array deque
• offerFirst(): inserts the specified element at the beginning of the array deque
• offerLast(): inserts the specified element at the end of the array deque

ArrayDeque<String> languages = new ArrayDeque<>();

languages.add(“English”);
languages.addFirst(“Hindi”);
languages.addLast(“French”);

System.out.println("ArrayDeque: " + languages);       // [Hindi, English, French]

2.2. Removing Elements

• remove(): returns and removes the first element of the array deque; if the deque is empty, this method throws NoSuchElementException.
• removeFirst(): returns and removes the first element from the array deque (equivalent to remove()), , if the deque is empty, this method throws NoSuchElementException.
• removeLast(): returns and removes the last element from the array deque; if the deque is empty, this method throws NoSuchElementException.
• poll(): returns and removes the first element of the array deque
• pollFirst(): returns and removes the first element of the array deque (equivalent to poll())
• pollLast(): returns and removes the last element of the array deque

ArrayDeque<String> languages = new ArrayDeque<>();

languages.add("English");
languages.add("Hindi");
languages.add("French");
languages.add("German");

System.out.println("ArrayDeque: " + languages);        // [English, Hindi, French, German]

String element = languages.remove();  // English
System.out.println("New ArrayDeque: " + languages);   // [Hindi, French, German]

String firstElement = languages.removeFirst();  // Hindi
String lastElement = languages.removeLast();  // German

// Reinitialize arraydeque again

String element = languages.poll(); // English  
System.out.println("New ArrayDeque: " + languages);   // [Hindi, French, German]

String firstElement = languages.pollFirst();  // Hindi
String lastElement = languages.pollLast();  // German

2.3. Accessing Elements

• getFirst(): returns the first element of the array deque; if the deque is empty, this method throws NoSuchElementException.
• getLast(): returns the last element of the array deque; if the deque is empty, this method throws NoSuchElementException.
• peek(): returns the first element of the array deque
• peekFirst(): returns the first element of the array deque (equivalent to peek())
• peekLast(): returns the last element of the array deque

String firstElement = languages.getFirst();  // English 

String lastElement = languages.getLast();  // German   

String element = languages.peek();  // English   

String firstElement = languages.peekFirst();    // English 

String lastElement = languages.peekLast();  // German

Notice that, there are two methods that can perform the same operation on ArrayDeque. For example, we can remove the last element from an ArrayDeque by using the removeLast() method or the pollLast() method. The difference between these methods is that one returns an exception if an ArrayDeque is empty while the other returns a null value.

Methods that return an exception in case ArrayDeque is full or empty are addFirst(), addLast(), removeFirst(), removeLast(), getFirst() and getLast().

ArrayDeque<String> queue = new ArrayDeque<>();

System.out.println(queue.removeLast());    // Exception in thread "main" java.util.NoSuchElementException

System.out.println(queue.pollLast());        // null

3. ArrayDeque as Stack

A Stack can be implemented using an ArrayDeque. We will choose one end of the Deque (front or rear) to insert and delete elements from this end only. We can either use the ArrayDeque methods for insertion and deletion or we can use the Stack class push() and pop() methods.

To implement LIFO (Last-In-First-Out), it is recommended to use a Deque over the Stack class. The ArrayDeque class is likely to be faster than the Stack class.

// Creating ArrayDeque that acts as Stack
Deque<Integer> stack = new ArrayDeque<Integer>();

// Pushing elements to Stack
stack.push(15);
stack.push(10);
stack.push(5);
System.out.println("Stack after insertion: " + stack);     // [5, 10, 15]
 
// Removing & Returning Stack elements
stack.pop();
System.out.println("Stack after deletion: " + stack);     // [10, 15]

stack.pop();
System.out.println("Stack after deletion: " + stack);     // [15]

4. ArrayDeque as Queue

We can implement a Queue using ArrayDeque by inserting elements at one end and removing them from the other. We can either use the ArrayDeque methods for insertion and deletion or we can use the Queue class add() and remove() methods. Queue implemented using it follows the same FIFO (First-In-First-Out).

// Creating ArrayDeque that acts as Queue
Deque<Integer> queue = new ArrayDeque<Integer>();

// Adding elements to Queue
queue.add(15);
queue.add(10);
queue.add(5);
System.out.println("Queue after insertion: " + queue);     // [15, 10, 5]

// Removing & Returning Queue elements
queue.remove();
System.out.println("Queue after deletion: " + queue);     // [10, 5]

queue. remove();
System.out.println("Queue after deletion: " + queue);     // [5]

5. Difference Between ArrayDeque and LinkedList

Both ArrayDeque and LinkedList implement the Deque interface. However, there exist some differences between the two; let’s see those differences.

• LinkedList supports null elements, whereas ArrayDeque doesn’t.
• LinkedList requires more storage than ArrayDeque as each node in a LinkedList includes links to other nodes.
• In terms of performance, ArrayDeque is likely to be faster than a LinkedList.

6. When to Use?

ArrayDeque implements as both Stack and Queue so we can use it in applications like maintaining web browser history, maintaining a list of undo operations in an application, in Job scheduling algorithms, etc.

 The problems where elements need to be removed and or added to both ends can be efficiently solved by using it. Also, it prefers to use ArrayDeque instead of Stack and LinkedList because of its faster performance.

One example where we can use a Deque is the A-Steal job scheduling algorithm. This algorithm implements task scheduling for several processors. A separate deque with threads maintains for each processor.

7. Conclusion

We have learned about ArrayDeque, its main features, its main methods, and practical examples. We have also seen how it has been implemented both as a Stack and as a Queue. Also covered some of the main differences between ArrayDeque and LinkedList and their practical use cases.

Happy Learning !!