Deep Dive (java.util) - ArrayDeque
The Faster Stack and Queue
"The data structure that makes LinkedList obsolete for stacks and queues."
ArrayDeque is a resizable circular buffer that implements Deque (double-ended queue). It's the fastest general-purpose stack and queue implementation in Java.
What is ArrayDeque, Really?
ArrayDeque is a circular array with two pointers — head and tail — that wrap around when they reach the ends. This gives O(1) insertion and removal at both ends.
Key constraint: ArrayDeque does NOT implement List. You cannot do get(index). If you need both Deque and indexed access, you're stuck with LinkedList.
The Circular Buffer
The core idea: the array wraps around. When head or tail reaches the end of the array, it wraps to the beginning.
transient Object[] elements; // Always a power of 2 in size
transient int head; // Index of the first element
transient int tail; // Index AFTER the last element
The Wrap-Around in Action
The elements wrap from index 7 → index 0. Logically, the deque contains [E, F, G, H] even though they're not contiguous in the array.
Index Arithmetic with Bitmask
Since the array size is always a power of 2, modular arithmetic uses bitmask instead of the expensive % operator:
// Power-of-2 size means: (index) & (length - 1) == index % length
// But & is much faster than %!
// Move head backwards (wrapping):
head = (head - 1) & (elements.length - 1);
// Move tail forward (wrapping):
tail = (tail + 1) & (elements.length - 1);
How addFirst() and addLast() Work
addFirst() — Move head backwards
public void addFirst(E e) {
if (e == null) throw new NullPointerException();
final Object[] es = elements;
es[head = (head - 1) & (es.length - 1)] = e; // Decrement head, wrap if needed
if (head == tail)
grow(1); // Full! Resize
}
addLast() — Move tail forwards
public void addLast(E e) {
if (e == null) throw new NullPointerException();
final Object[] es = elements;
es[tail] = e;
if ((tail = (tail + 1) & (es.length - 1)) == head)
grow(1); // Full! Resize
}
Both operations are O(1) — just one array write and one index update.
How pollFirst() and pollLast() Work
public E pollFirst() {
final Object[] es = elements;
final int h = head;
E e = (E) es[h];
if (e != null) {
es[h] = null; // Help GC
head = (h + 1) & (es.length - 1); // Advance head
}
return e;
}
public E pollLast() {
final Object[] es = elements;
final int t = (tail - 1) & (es.length - 1);
E e = (E) es[t];
if (e != null) {
es[t] = null; // Help GC
tail = t; // Retreat tail
}
return e;
}
Both are O(1) — one null assignment and one index update.
5. Resizing — When the Circle Gets Full
When head == tail after an insertion, the array is full. ArrayDeque doubles it:
private void grow(int needed) {
final int oldCapacity = elements.length;
int newCapacity = oldCapacity + (oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1);
// Small arrays: roughly double
// Large arrays: grow by 50%
final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
// ... handle wrap-around during copy
}
During resize, the wrap-around is "unwrapped" — elements are rearranged so head starts at index 0 in the new array.
6. ArrayDeque as a Stack
ArrayDeque is the recommended Stack implementation (over java.util.Stack):
// ✅ ArrayDeque as a Stack (LIFO)
Deque<String> stack = new ArrayDeque<>();
stack.push("first"); // addFirst()
stack.push("second"); // addFirst()
stack.push("third"); // addFirst()
stack.peek(); // "third" — top of stack (peekFirst)
stack.pop(); // "third" — removes top (removeFirst)
stack.pop(); // "second"
stack.pop(); // "first"
Why not
java.util.Stack? It extendsVector(synchronized), is slow, and exposes random-access methods that break the Stack abstraction.ArrayDequeis faster and cleaner.
ArrayDeque as a Queue
// ✅ ArrayDeque as a Queue (FIFO)
Deque<String> queue = new ArrayDeque<>();
queue.offer("first"); // addLast()
queue.offer("second"); // addLast()
queue.offer("third"); // addLast()
queue.peek(); // "first" — front of queue (peekFirst)
queue.poll(); // "first" — removes front (pollFirst)
queue.poll(); // "second"
queue.poll(); // "third"
8. Why ArrayDeque Beats LinkedList
| Aspect | ArrayDeque | LinkedList |
|---|---|---|
| addFirst/addLast | O(1) amortized | O(1) |
| pollFirst/pollLast | O(1) | O(1) |
| Cache locality | Excellent (contiguous array) | Terrible (scattered nodes) |
| Memory per element | ~4-8 bytes (just a reference) | ~32 bytes (Node object) |
| GC pressure | Low (one array) | High (one Node per element) |
| Null elements | ❌ Not allowed | ✅ Allowed |
| List interface | ❌ Not implemented | ✅ Implemented |
In benchmarks, ArrayDeque is typically 3-4x faster than LinkedList for stack/queue operations due to cache locality and lower memory overhead.
Performance Characteristics
| Operation | Time Complexity | Notes |
|---|---|---|
addFirst(e) |
O(1) amortized | May trigger resize |
addLast(e) |
O(1) amortized | May trigger resize |
pollFirst() |
O(1) | Always constant |
pollLast() |
O(1) | Always constant |
peekFirst() |
O(1) | |
peekLast() |
O(1) | |
size() |
O(1) | Computed from head/tail |
contains(Object) |
O(n) | Linear scan |
remove(Object) |
O(n) | Linear scan + shift |
| Iteration | O(n) | Cache-friendly traversal |
Common Pitfalls
Pitfall 1: Null Elements Not Allowed
// ❌ NullPointerException!
ArrayDeque<String> deque = new ArrayDeque<>();
deque.add(null); // Throws NPE!
// This is because null is used as the sentinel for "empty slot" in the array.
// If nulls were allowed, poll() couldn't distinguish "empty" from "null element".
Pitfall 2: No Random Access
// ❌ ArrayDeque does NOT implement List
ArrayDeque<String> deque = new ArrayDeque<>();
deque.add("hello");
// deque.get(0); // Compile error! No get(index) method.
// If you need index access + deque operations, you must use LinkedList
Pitfall 3: Not Thread-Safe
// ❌ Not safe for concurrent access
// ✅ Use ConcurrentLinkedDeque or wrap with synchronization
Summary
The one-liner: ArrayDeque is a circular buffer providing O(1) add/remove at both ends with 8x less memory and 3-4x more speed than LinkedList — the default choice for stacks and queues.