ArrayDeque in Java is a class that implements a Deque interface. It’s an array-based implementation of a double-ended queue. As the name suggests, a double-ended queue is a queue that allows us to add or remove items from both front and rear ends.
Before we dive in, let’s quickly look at a few noteworthy points on an ArrayDeque:
We can use one of the following constructors to instantiate an ArrayDeque:
//creates an empty ArrayDeque with default capacity of 16 ArrayDeque() //creates an ArrayDeque with all the elements present in the given collection ArrayDeque(Collection c) /* *constructs an empty ArrayDeque with a capacity sufficient * to hold given number of elements */ ArrayDeque(int numElements)
The most common operations we perform on a data-structure involve insertion, retrieval, and removal. Here, we have two groups of methods for each of those operations.
For one group of methods, we get an exception if the operation fails. The other group of methods will simply return a special value indicating the status of the operation.
Let’s explore these methods:
|Operation||At the Head||At the Tail|
|Throws Exception||Returns special value||Throws Exception||Returns special value|
|Insertion||void addFirst(e)||boolean offerFirst(e)||void addLast(e)||boolean offerLast(e)|
|Retrieval||E getFirst()||E peekFirst()||E getLast()||E peekLast()|
|Removal/Deletion||E removeFirst()||E pollFirst()||E removeLast()||E pollLast()|
The addFirst()/offerFirst() methods add an element to the front side of the Deque. Similarly, addLast()/offerLast() methods add an element to the end. The difference between these two flavors is:
However, ArrayDeque is an unbounded deque implementation. And so, offerFirst()/addFirst() and offerLast()/addLast() methods behave the same way. They simply add an element to the front or back based on their usage:
Deque<Integer> dq = new ArrayDeque<>(); dq.addFirst(1); dq.addLast(2); dq.offerFirst(3); dq.offerLast(4); System.out.println(dq); //[3, 1, 2, 4]
The getFirst()/getLast() Or peekFirst()/peekLast() methods will return the first and the last element respectively, without removing it:
Deque<Integer> dq = new ArrayDeque(); dq.addFirst(1); dq.addFirst(2); System.out.println(dq.getFirst() + ":" + dq.peekFirst()); //2:2 System.out.println(dq.getLast() + ":" + dq.peekLast()); //1:1
Note that the getFirst()/getLast() methods will throw an exception when invoked on an empty deque. However, the peekFirst()/peekLast() methods will return null if the deque is empty:
Deque<Integer> dq = new ArrayDeque<>(); // empty deque Integer val1 = dq.getFirst(); //throws NoSuchElementException Integer val2 = dq.peekFirst(); // null
To remove an element from a Deque, we can either use:
Deque<Integer> dq = new ArrayDeque<>(); dq.addLast(1); dq.addLast(2); Integer val1 = dq.removeFirst(); //1 System.out.println(dq); // Integer val2 = dq.pollFirst(); //2 System.out.println(dq); // val1 = dq.removeFirst(); // will throw a NoSuchElementException val2 = dq.pollFirst(); // null
Let’s look at some of the other commonly used methods:
In this tutorial, we learned about a popular Deque implementation class known as an ArrayDeque.
As per Javadocs, this class is likely to be faster than Stack when used as a stack. Also, it’s likely to be faster than LinkedList when used as a queue. Most ArrayDeque operations, the ones that operate on either front or rear end, have an amortized cost of O(1).