ArrayDeque Class in Java - Quiz

ArrayDeque (java.util, since Java 6) is an implementation of the Deque interface on top of a resizable circular array. Inside there is an Object[] array and two indexes: head and tail. The array is treated as a ring: when addFirst() moves the index below zero, the element goes into the last cell. That is why adding and removing at either end never shifts the other elements and takes amortized O(1) time.

Deque<String> deque = new ArrayDeque<>();
deque.addLast("A");
deque.addLast("B");
deque.addLast("C");
deque.addFirst("Z");
System.out.println(deque); // [Z, A, B, C]

This is the difference from ArrayList: a list always keeps its data starting at index 0, so add(0, e) and remove(0) shift the whole array — O(n). In exchange, ArrayDeque has no index access.

There are three constructors:

• ArrayDeque() — an empty deque that holds 16 elements before it has to grow;
• ArrayDeque(int numElements) — an empty deque with room for numElements elements; a negative or zero value throws nothing: new ArrayDeque<>(-5) creates a deque with the minimum capacity (while new ArrayList<>(-5) throws IllegalArgumentException);
• ArrayDeque(Collection<? extends E> c) — a copy of the elements of c in the order of its iterator; a null inside c causes NullPointerException.

Capacity is the size of the internal array, not a limit: new ArrayDeque<>(100) accepts the 101st element just as well, the array is simply reallocated. Pass an initial capacity when you know the size in advance — it saves the extra copying. In Java 8 the capacity was rounded up to a power of two and doubled; in modern JDKs the array roughly doubles while it is smaller than 64 cells and grows by 50% after that. The array never shrinks and there is no trimToSize(); to release memory after a peak load, make a copy: deque = new ArrayDeque<>(deque);. A hard size limit comes from the queues of java.util.concurrent, for example ArrayBlockingQueue.

Operations at the ends — addFirst()/addLast(), offer*(), push(), poll*(), remove*(), pop(), peek*(), get*(), plus size() and isEmpty() — run in O(1); adding is amortized O(1) and O(n) at the moment the array grows. Anything that searches for an element inside — contains(o), remove(o), removeFirstOccurrence(o), removeLastOccurrence(o), removeIf(), iterator().remove() — is O(n). clone() and toArray() copy the array in O(n), but not the elements themselves (a shallow copy).

On an empty deque poll*() and peek*() return null, while remove*(), pop(), get*() and element() throw NoSuchElementException. offer*() always return true: there is no capacity limit. ArrayDeque has no index-based methods (get(int), set(int, E)); the only public method it adds on top of the interfaces is clone().

Empty cells of the circular array are marked with null, and poll() and peek() return null to signal an empty deque, so null cannot be stored. The ban applies only to writing: offer(null), push(null), addLast(null) and the copy constructor with a null inside throw NullPointerException, while contains(null) and remove(null) simply return false. If you need null elements, use LinkedList.

ArrayDeque does not override equals() and hashCode(), so two deques with the same elements are not equal: references are compared. For the same reason a deque cannot serve as a HashMap key or a HashSet element if you expect content-based comparison. Compare contents through copies; the head-to-tail order is preserved:

Deque<Integer> a = new ArrayDeque<>(List.of(1, 2, 3));
Deque<Integer> b = new ArrayDeque<>(List.of(1, 2, 3));
System.out.println(a.equals(b));                                // false
System.out.println(List.copyOf(a).equals(List.copyOf(b)));      // true
System.out.println(Arrays.equals(a.toArray(), b.toArray()));    // true

No. If two threads add or remove elements at the same time, the head and tail indexes can get out of sync with the array contents, and elements are lost. For a queue shared between threads use ConcurrentLinkedDeque or the blocking LinkedBlockingDeque. There is no Collections.synchronizedDeque() wrapper, and Collections.synchronizedCollection(deque) returns a plain Collection without push() or pollFirst().

The iterators of ArrayDeque are fail-fast: if the deque is modified during iteration other than through iterator.remove(), the iterator usually throws ConcurrentModificationException. This is a best-effort check: the exception is not guaranteed, so program logic must never depend on it. To remove elements while iterating, use the iterator or removeIf():

Deque<Integer> deque = new ArrayDeque<>(List.of(1, 2, 3, 4));
deque.removeIf(x -> x % 2 == 0);
System.out.println(deque); // [1, 3]

The Java documentation states that ArrayDeque is likely to be faster than Stack when used as a stack and faster than LinkedList when used as a queue. LinkedList is O(1) at the ends too, but every insertion creates a node object, and the nodes are scattered across memory and load the garbage collector; ArrayDeque writes a reference into a ready array cell, and neighbouring elements sit next to each other in the CPU cache. Stack extends Vector: every method is synchronized, and get(i) breaks the stack principle; it belongs only in legacy code.

So ArrayDeque is the default choice for a stack (undo history, depth-first search, expression parsing, bracket checking) and for a FIFO queue (breadth-first search, a task buffer, a sliding window of the last N values) in single-threaded code. Pick another implementation only when a requirement contradicts its properties:

• you need to store null or need the List interface — LinkedList;
• you need index access — ArrayList;
• elements must come out by priority — PriorityQueue;
• the queue is shared between threads — ConcurrentLinkedDeque, LinkedBlockingDeque;
• you need a hard size limit — ArrayBlockingQueue, LinkedBlockingDeque(capacity).