Introduction:
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:
- An ArrayDeque has no capacity constraints; the size of the array grows dynamically as per needs
- We can’t add null values to an ArrayDeque
- It’s not a thread-safe implementation
- Since Deque is double-ended, we can use it either as a Stack or a Queue
Instantiating 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)
ArrayDeque Operations:
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() |
1. Insertion:
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:
- addFirst()/addLast() methods throw an exception in case of capacity violations
- offerFirst()/offerLast() methods simply return false for a capacity violation
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]
2. Retrieval:
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
3. Deletion:
To remove an element from a Deque, we can either use:
- removeFirst()/removeLast(): removes first/last element from the deque respectively. These methods will throw an exception if deque is empty, Or
- pollFirst()/pollLast(): removes first/last element from the deque respectively. They’ll return null for an empty deque
Deque<Integer> dq = new ArrayDeque<>(); dq.addLast(1); dq.addLast(2); Integer val1 = dq.removeFirst(); //1 System.out.println(dq); //[2] Integer val2 = dq.pollFirst(); //2 System.out.println(dq); //[] val1 = dq.removeFirst(); // will throw a NoSuchElementException val2 = dq.pollFirst(); // null
4. Other Methods:
Let’s look at some of the other commonly used methods:
- void push(E e): pushes an element onto the top of stack representation of deque
- E pop(): pops off an element on the top of stack representation of the deque
- boolean isEmpty(): returns true for an empty deque
- int size(): returns the number of elements the deque holds
- boolean contains(Object obj): returns true if the given object is present in the deque
- void clear(): removes all deque elements
- E remove(): returns and removes the head element
- boolean removeFirstOccurrence(E e): traverses the deque from head to tail and removes the first occurrence of the specified element
- boolean removeLastOccurrence(E e): removes the last occurrence of the specified element
Conclusion:
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).
Published on Java Code Geeks with permission by Shubhra Srivastava, partner at our JCG program. See the original article here: Java ArrayDeque Opinions expressed by Java Code Geeks contributors are their own. |
