☕ JavaCollections Framework

ArrayDeque

ArrayDeque is the recommended general-purpose Deque implementation in Java. It is backed by a resizable circular array that provides O(1) amortised time for all head and tail operations — addFirst, addLast, pollFirst, pollLast, peekFirst, peekLast. ArrayDeque is faster than LinkedList for deque and queue operations because it avoids per-element node allocation and achieves better cache locality. It is faster than the legacy Stack class because it has no synchronisation overhead. The circular array design allows both ends to advance efficiently without shifting elements. This entry covers the circular array internals, performance characteristics, the resizing strategy, practical usage as both stack and queue, and the scenarios where ArrayDeque is the correct default choice.

Circular Array Internals

ArrayDeque is backed by an array and two pointers: head (pointing to the first element) and tail (pointing just past the last element). The array is used as a circular buffer — when the tail pointer reaches the end of the array, it wraps around to index 0. This allows both addFirst and addLast to operate by simply decrementing or incrementing the respective pointer modulo the array length, without shifting any existing elements. addFirst decrements the head pointer (with wraparound) and stores the new element at that index. addLast stores the new element at the tail index and increments tail (with wraparound). pollFirst reads the element at head, increments head (with wraparound), and clears the slot. pollLast reads the element at tail-1, decrements tail, and clears the slot. All four operations are O(1) with no element movement. The array capacity is always a power of two. This is not an accident — it enables the modulo operation (index & (capacity-1)) to be implemented as a fast bitwise AND instead of division. The head and tail pointers are maintained as raw indices; the effective index is always (pointer & (capacity-1)). When head equals tail, the deque is empty. The capacity is always maintained at least one larger than the size to distinguish empty from full. When the deque fills its array, ArrayDeque doubles its capacity. It allocates a new array of double the size, copies all elements to the beginning of the new array (linearising the circular buffer), and resets head to 0 and tail to the old size. This doubling strategy gives O(1) amortised time for insertions — n insertions total cost O(n), so O(1) per insertion amortised.

Java

// ── Circular array visualisation ──────────────────────────────────────
//
// Circular array with capacity=8, initially empty:
// [ _, _, _, _, _, _, _, _ ]
//   ^head=0  ^tail=0   (empty: head==tail)
//
// addLast("A"):
// [ A, _, _, _, _, _, _, _ ]
//   ^head=0    tail=1^
//
// addLast("B"), addLast("C"):
// [ A, B, C, _, _, _, _, _ ]
//   ^head=0          tail=3^
//
// addFirst("Z"):  head wraps to index 7
// [ A, B, C, _, _, _, _, Z ]
//   tail=3^      ^head=7  (decremented with wraparound)
//
// pollFirst():   removes Z (head index 7), head wraps back to 0
// [ A, B, C, _, _, _, _, _ ]
//   ^head=0   tail=3^
//
// Key insight: no element shifting — only pointer arithmetic

// ── ArrayDeque construction ───────────────────────────────────────────
// Default initial capacity: 16 (Java 11+, was 8 in earlier versions)
ArrayDeque<String> deque1 = new ArrayDeque<>();

// With initial capacity hint (avoids resizing for known sizes):
ArrayDeque<String> deque2 = new ArrayDeque<>(100);

// Constructed from collection (adds in iteration order):
ArrayDeque<String> deque3 = new ArrayDeque<>(List.of("a", "b", "c"));

// ── Internal representation — capacity always power of 2 ──────────────
// The implementation ensures capacity is always 2^n
// This enables fast modulo: index = pointer & (capacity - 1)
// Instead of: index = pointer % capacity  (slower division)
//
// Capacity progression: 16 → 32 → 64 → 128 → ...
// Triggered by: addFirst or addLast when (tail == head) after increment

// ── Wraparound arithmetic ──────────────────────────────────────────────
// For a deque with capacity=8:
// head at index 1, tail at index 4:  [_, A, B, C, _, _, _, _]
//
// addFirst("Z"): head = (1 - 1) & 7 = 0  → [Z, A, B, C, _, _, _, _]
// addFirst("Y"): head = (0 - 1) & 7 = 7  → [Z, A, B, C, _, _, _, Y] (wraps!)
//
// pollFirst(): removes index 7 (Y), head = (7 + 1) & 7 = 0
// Result: head=0, deque=[Z, A, B, C]

Performance — Comparison with LinkedList and Stack

ArrayDeque is consistently faster than LinkedList for deque and queue operations. The reasons are architectural: LinkedList allocates a new Node object for every added element (three objects per add: the element wrapper, the node's prev pointer, the node's next pointer), while ArrayDeque simply writes to an existing array slot. This difference matters at high insertion rates because object allocation drives GC pressure — fewer allocations means fewer collections. Cache performance further favours ArrayDeque. The circular array stores elements contiguously in memory. Iterating through an ArrayDeque traverses adjacent cache lines. LinkedList's elements are scattered across the heap in individually allocated nodes; iterating requires following a chain of pointers to non-adjacent memory addresses, causing cache misses at each step. For queues processed in FIFO order (a common pattern), ArrayDeque's sequential access pattern is optimal for CPU caches. The performance of ArrayDeque vs LinkedList depends on what is being measured. For addFirst/addLast/pollFirst/pollLast, ArrayDeque wins decisively in both throughput and latency. For random access (get(int index)), LinkedList is equally poor (O(n) linear scan) — neither structure supports efficient random access. For removing from the middle (Iterator.remove()), LinkedList wins with O(1) after reaching the element, whereas ArrayDeque requires shifting elements. But removing from the middle of either structure is an unusual operation for queue and stack use cases. Compared to the legacy Stack (extends Vector), ArrayDeque is dramatically faster for stack operations. Vector's methods are all synchronised — every push and pop acquires and releases a lock even in single-threaded code. ArrayDeque has zero synchronisation overhead.

Java

// ── Performance benchmark context ────────────────────────────────────
// Typical relative throughput for 10 million operations (single-threaded):
//
// Operation          ArrayDeque    LinkedList    Stack (Vector)
// ──────────────────────────────────────────────────────────────
// offer/addLast      ~3.5B ops/s   ~1.2B ops/s  ~0.3B ops/s
// poll/removeFirst   ~3.0B ops/s   ~1.0B ops/s  ~0.3B ops/s
// push (addFirst)    ~3.5B ops/s   ~1.2B ops/s  ~0.3B ops/s
// pop (removeFirst)  ~3.0B ops/s   ~1.0B ops/s  ~0.3B ops/s
//
// ArrayDeque is ~3x faster than LinkedList and ~10x faster than Stack
// for typical stack/queue operations

// ── Memory usage comparison ───────────────────────────────────────────
// For 1 million String elements:
//
// ArrayDeque:
//   Array of 2^21 = 2,097,152 reference slots × 8 bytes = 16MB
//   + ArrayDeque object header (~32 bytes)
//   = ~16MB total (low overhead)
//
// LinkedList:
//   1,000,000 Node objects × ~48 bytes each = ~48MB
//   (each Node: 16B header + 8B prev + 8B next + 8B element = 40B + padding)
//   = ~3x more memory than ArrayDeque

// ── When to use each ─────────────────────────────────────────────────
// ArrayDeque:
//   ✓ Stack operations (push/pop from front)
//   ✓ Queue operations (offer tail, poll head)
//   ✓ Deque operations (both ends)
//   ✓ Single-threaded use
//   ✓ Memory efficiency matters
//   ✓ Default choice in almost all cases
//
// LinkedList:
//   ✓ Frequent removal from the MIDDLE during iteration
//   ✓ Already using as List AND queue (both interfaces needed)
//   ✗ Never preferred over ArrayDeque for pure queue/stack use
//
// Stack (legacy):
//   ✗ Never use in new code — use ArrayDeque instead
//
// Collections.synchronizedDeque(new ArrayDeque<>()):
//   ✓ Simple thread safety needed, low concurrency
//
// LinkedBlockingDeque:
//   ✓ Multi-threaded access, blocking semantics needed
//   ✓ Bounded capacity for backpressure

Common Patterns and Idioms

ArrayDeque as a stack is the most direct replacement for the legacy Stack class. Declare it as Deque<T> (not ArrayDeque<T>) to program to the interface, but instantiate it as ArrayDeque. Use push()/pop()/peek() for LIFO semantics. This gives the same API as Stack without synchronisation overhead and without the inappropriate List interface methods. ArrayDeque as a queue uses offer()/poll()/peek() (which map to offerLast/pollFirst/peekFirst). Declare it as Queue<T> if the code only needs queue operations, giving flexibility to substitute other Queue implementations. The null restriction is important: unlike LinkedList, ArrayDeque throws NullPointerException when null is offered or added. This is actually safer — it prevents the poll()-returns-null ambiguity. One important limitation: ArrayDeque is not synchronized. It is not thread-safe for concurrent access without external synchronisation. For concurrent queue and deque needs, use java.util.concurrent.ConcurrentLinkedDeque (non-blocking, unbounded) or java.util.concurrent.LinkedBlockingDeque (blocking, optionally bounded). The only correct way to use ArrayDeque concurrently is with explicit external synchronisation, which is usually a sign that a concurrent data structure should be used instead. ArrayDeque does not support null elements. This restriction is intentional and beneficial: poll() returning null unambiguously means the deque was empty, not that null was the head element. This eliminates the awkward null check that is needed with LinkedList-based queues.

Java

// ── ArrayDeque as a stack — recommended pattern ─────────────────────
// Declare as Deque<T> — programs to interface, not implementation
Deque<Integer> stack = new ArrayDeque<>();

stack.push(1);   // addFirst(1) — [1]
stack.push(2);   // addFirst(2) — [2, 1]
stack.push(3);   // addFirst(3) — [3, 2, 1]

System.out.println(stack.peek());  // 3 — top of stack, no removal
System.out.println(stack.pop());   // 3 — removed
System.out.println(stack.pop());   // 2 — removed

// Safe pop with isEmpty check:
while (!stack.isEmpty()) {
    System.out.println(stack.pop());
}

// ── ArrayDeque as a queue — recommended pattern ──────────────────────
// Declare as Queue<T> if only queue operations are needed
Queue<String> queue = new ArrayDeque<>();

queue.offer("first");    // addLast — null-safe, returns false if full
queue.offer("second");
queue.offer("third");

System.out.println(queue.peek());    // "first" — no removal
System.out.println(queue.poll());    // "first" — removed
System.out.println(queue.size());    // 2

// Process all items:
while (!queue.isEmpty()) {
    process(queue.poll());
}

// ── Null is prohibited ────────────────────────────────────────────────
ArrayDeque<String> deque = new ArrayDeque<>();
// deque.offer(null);    // NullPointerException — prohibited
// deque.push(null);     // NullPointerException — prohibited
// deque.addFirst(null); // NullPointerException — prohibited
// This is SAFER than LinkedList which accepts null:
String result = deque.poll();  // null means EMPTY — unambiguous

// ── Full Deque usage — both ends ──────────────────────────────────────
Deque<String> workList = new ArrayDeque<>();

// Urgent items go to front, normal items go to back
workList.offerLast("normal-task-1");
workList.offerLast("normal-task-2");
workList.offerFirst("urgent-task");   // jumps to front

System.out.println(workList.pollFirst());   // "urgent-task"
System.out.println(workList.pollFirst());   // "normal-task-1"
System.out.println(workList.pollFirst());   // "normal-task-2"

// ── Iterating — in logical order (head to tail) ───────────────────────
Deque<Integer> nums = new ArrayDeque<>(List.of(1, 2, 3, 4, 5));

// Forward (head to tail):
for (int n : nums) {
    System.out.print(n + " ");   // 1 2 3 4 5
}

// Reverse (tail to head) using descending iterator:
Iterator<Integer> reverse = nums.descendingIterator();
while (reverse.hasNext()) {
    System.out.print(reverse.next() + " ");  // 5 4 3 2 1
}

Resizing and Capacity Management

ArrayDeque grows by doubling its capacity when it becomes full. The doubling strategy ensures O(1) amortised insertion: if the array is grown from capacity n to 2n, n elements are copied. But the n insertions that preceded the resize each cost O(1), so the total cost for n+1 insertions is O(n) + O(n) = O(n), giving O(1) amortised per insertion. When resizing, ArrayDeque linearises its circular buffer. The head pointer becomes 0, the tail pointer becomes the old size, and elements are laid out sequentially from index 0. This is necessary because the new array has a different capacity (and thus different wraparound behaviour), so the existing indices are no longer valid. The initial capacity can be provided to the constructor as a hint. If the final size is known or estimated, providing a sufficiently large initial capacity avoids all resize operations. Providing a capacity hint does not set a maximum — ArrayDeque will still grow beyond the initial capacity if needed. For memory-sensitive applications where a hard bound on queue size is required, ArrayBlockingQueue (a bounded blocking queue) is the appropriate choice rather than a capacity-constrained ArrayDeque. There is no shrinking. ArrayDeque does not reduce its array when elements are removed. If 1,000,000 elements are added and then removed, the underlying array remains at 2^20 capacity. For applications that experience large temporary queues followed by extended quiet periods, this can leave significant memory allocated but unused. In such cases, creating a new ArrayDeque and discarding the old one (or using trimToSize on other collections that support it) may be appropriate.

Java

// ── Capacity hint for known size ─────────────────────────────────────
// If processing exactly 10,000 tasks:
Deque<Task> taskQueue = new ArrayDeque<>(10_000);
// Avoids multiple resize operations during the initial fill

// If size unknown but expected large:
Deque<LogEntry> logQueue = new ArrayDeque<>(4096);  // good starting size

// ── Resizing behaviour ────────────────────────────────────────────────
// new ArrayDeque()        → initial capacity 16 (Java 11+)
// After 16 adds:          → resize to 32
// After 32 adds:          → resize to 64
// After 1024 adds:        → resize to 2048
// etc.
//
// Total copy cost for n adds = 16 + 32 + 64 + ... + n = O(n)
// Amortised cost per add = O(n)/n = O(1)

// ── No shrinking — memory impact ──────────────────────────────────────
Deque<byte[]> largeQueue = new ArrayDeque<>();

// Fill with 100,000 large objects:
for (int i = 0; i < 100_000; i++) {
    largeQueue.offer(new byte[1024]);   // queue grows to capacity ~131,072
}

// Drain all elements:
while (!largeQueue.isEmpty()) {
    largeQueue.poll();   // elements removed, but array stays at ~131,072 slots
}
// Memory for ~131,072 reference slots is still allocated!
// (~1MB of reference array, not counting the byte[] objects themselves)

// If persistent large memory use is a problem, replace with fresh deque:
largeQueue = new ArrayDeque<>();   // old deque eligible for GC, fresh one allocated

// ── Checking current capacity (not directly available) ────────────────
// ArrayDeque does not expose capacity() — only size()
// To estimate: after filling, capacity >= next power of 2 above size
Deque<Integer> d = new ArrayDeque<>();
for (int i = 0; i < 100; i++) d.offer(i);
System.out.println(d.size());  // 100
// Internal capacity is 128 (next power of 2 above 100)

// ── Thread safety — ArrayDeque is NOT thread-safe ─────────────────────
// For concurrent use, do NOT synchronise ArrayDeque externally in general —
// use purpose-built concurrent implementations:

// Option 1: ConcurrentLinkedDeque — non-blocking, high throughput
Deque<Task> concurrent1 = new ConcurrentLinkedDeque<>();

// Option 2: LinkedBlockingDeque — blocking, optionally bounded
BlockingDeque<Task> concurrent2 = new LinkedBlockingDeque<>(1000);

// Option 3: Synchronised wrapper (low concurrency only)
Deque<Task> concurrent3 =
    (Deque<Task>) Collections.synchronizedCollection(new ArrayDeque<>());
// Note: iteration still requires external synchronisation

ArrayDeque

Circular Array Internals

Performance — Comparison with LinkedList and Stack

Common Patterns and Idioms

Resizing and Capacity Management

Related Topics in Collections Framework