Java ArrayDeque

java.util.ArrayDeque<E> is the collection the Java documentation explicitly recommends over both java.util.Stack and java.util.LinkedList for all queue and stack use cases. It is a concrete implementation of the Deque interface backed by a resizable circular array. No per-element object allocation, no synchronisation overhead, no wasted traversals for head operations — just direct array index arithmetic at both ends.

Every time a senior developer reviews code and replaces new Stack<>() with new ArrayDeque<>(), this is why.

What Is Java ArrayDeque?

ArrayDeque<E> is a concrete class in java.util that implements Deque<E>. It stores elements in a single resizable Object[] array using a circular buffer with two integer pointers — head and tail — that wrap around the array boundaries. This structure gives O(1) amortised operations at both ends simultaneously without the pointer-chasing penalty of LinkedList.

The diagram below shows where ArrayDeque sits in the Collections hierarchy.

java.lang.Iterable<E>
    └── java.util.Collection<E>
            └── java.util.Queue<E>          ← FIFO contract
                    └── java.util.Deque<E>  ← double-ended: both-end access
                            ├── ArrayDeque  ← THIS CLASS: circular resizable array
                            └── LinkedList  ← doubly-linked nodes, also implements List

KEY FACTS:
  Package         : java.util
  Since           : Java 1.6
  Implements      : Deque<E>, Cloneable, Serializable
  Backing store   : Object[] with circular head/tail indices
  Null            : NOT allowed — NullPointerException on any null insertion
  Duplicates      : allowed
  Thread-safe     : NO — use LinkedBlockingDeque for concurrent access
  Default capacity: 16 elements (internal — not configurable in the same way as ArrayList)
  Resize strategy : approximately double, always a power of 2

Basic Overview — The Full ArrayDeque API

ArrayDeque exposes every method in the Deque interface plus a few additions. All operations at both ends are O(1) amortised.

ARRAYDEQUE COMPLETE METHOD REFERENCE:

  HEAD OPERATIONS (front of deque):
    addFirst(e)    / offerFirst(e)  ← insert at head (throws / returns false)
    removeFirst()  / pollFirst()    ← remove from head (throws / returns null)
    getFirst()     / peekFirst()    ← inspect head (throws / returns null)

  TAIL OPERATIONS (back of deque):
    addLast(e)     / offerLast(e)   ← insert at tail (throws / returns false)
    removeLast()   / pollLast()     ← remove from tail (throws / returns null)
    getLast()      / peekLast()     ← inspect tail (throws / returns null)

  STACK ALIASES (all operate on head):
    push(e)  = addFirst(e)
    pop()    = removeFirst()
    peek()   = peekFirst()

  QUEUE ALIASES (standard Queue contract):
    add(e)     = addLast(e)
    offer(e)   = offerLast(e)
    remove()   = removeFirst()
    poll()     = pollFirst()
    element()  = getFirst()
    peek()     = peekFirst()

  ITERATION:
    iterator()            ← head → tail (front to back)
    descendingIterator()  ← tail → head (back to front, unique to Deque)

  SIZE:
    size(), isEmpty(), clear(), contains(e), toArray()

PRODUCTION RULE:
  Always prefer the null-returning variants:
    offerFirst, offerLast, pollFirst, pollLast, peekFirst, peekLast
  These never throw on empty — empty deque is a normal operating condition.

When to Use ArrayDeque

USE ArrayDeque WHEN:
  1. A LIFO stack is needed — always prefer over java.util.Stack
     Stack.push()/pop() acquire a mutex on every call (synchronized from Vector)
     ArrayDeque.push()/pop() have zero synchronisation cost

  2. A FIFO queue is needed — prefer over LinkedList
     LinkedList allocates a Node object per element; ArrayDeque does not
     ArrayDeque's contiguous array has better CPU cache locality

  3. Both-end access is needed on the same collection
     — sliding window algorithms, palindrome check, monotone deque
     — work-stealing schedulers, undo-redo history with fixed-size window

  4. Memory and GC pressure matter
     — no per-element Node → smaller heap footprint
     — fewer short-lived objects for GC to collect

CHOOSE LinkedList (as Deque) ONLY WHEN:
  - Both Deque and List interfaces are needed on the same reference
  - get(index) or set(index, e) or subList() required alongside deque operations
  - Null elements must be stored (ArrayDeque rejects null; LinkedList allows it)

CHOOSE LinkedBlockingDeque WHEN:
  - Multiple producer/consumer threads share the deque
  - Blocking takeFirst()/takeLast() that wait on empty is needed

NEVER USE java.util.Stack IN NEW CODE:
  - Synchronized on every operation even in single-threaded programs
  - Inherits Vector's get(index)/set(index) which break stack encapsulation
  - Java documentation explicitly recommends ArrayDeque as the replacement

How ArrayDeque Works Internally

The Circular Array and Head/Tail Mechanics

The core insight is that ArrayDeque treats its internal array as a circle. head and tail are integer indices that advance on opposite sides — head moves backward on addFirst (or forward on pollFirst), tail moves forward on addLast.

INITIAL STATE (empty ArrayDeque, capacity 16):
  elements: [ null × 16 ]
  head = 0,  tail = 0

AFTER addLast("A"), addLast("B"), addLast("C"):
  elements: [ "A" | "B" | "C" | null | null | ... | null ]
               0     1     2     3     4        15
  head = 0,  tail = 3

AFTER addFirst("Z") — insert BEFORE head:
  head = (0 - 1) & 15 = 15       ← bitwise wrap to last slot
  elements[15] = "Z"
  elements: [ "A" | "B" | "C" | null | ... | null | "Z" ]
               0     1     2     3           14     15
  head = 15, tail = 3

  Logical deque order: Z, A, B, C
  (read from head=15 → wraps at 0 → continues to tail-1=2)

AFTER pollFirst() — remove "Z":
  result = elements[15] = "Z"
  elements[15] = null            ← clear slot (helps GC)
  head = (15 + 1) & 15 = 0
  head = 0, tail = 3

  Logical deque order: A, B, C

BITWISE MASK: (index) & (capacity - 1)
  Capacity is always a power of 2 (16, 32, 64...).
  capacity - 1 is all-ones in binary (e.g., 15 = 0b1111).
  Any index & mask naturally wraps around — faster than modulo.
  Example: (15 + 1) & 15 = 16 & 15 = 0  (wraps to front)
           (0 - 1)  & 15 = -1 & 15 = 15 (wraps to back)

Resize — When and How

ArrayDeque resizes when the circular buffer becomes full — that is, when head == tail after an insertion. The resize copies elements in logical order (head to end, then 0 to tail-1) into a new array of double the capacity.

RESIZE SCENARIO (capacity 8, all 8 slots occupied):

  Before resize:
  elements: [ "E" | "F" | "G" | "H" | "A" | "B" | "C" | "D" ]
               0     1     2     3     4     5     6     7
  head = 4,  tail = 4  (full — head == tail)

  Logical order: A, B, C, D, E, F, G, H
  (starting at head=4, wrapping around)

  addLast("I") triggers resize:
    1. Allocate new Object[16]
    2. Copy elements from head (index 4) to end of old array → [A,B,C,D]
    3. Copy elements from index 0 to tail-1 (index 3) → [E,F,G,H]
    4. Result: new[0..7] = [A,B,C,D,E,F,G,H]
    5. Insert "I" at new[8]
    6. head = 0, tail = 9

  After resize:
  elements: [ "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | null×7 ]
               0     1     2     3     4     5     6     7     8
  head = 0,  tail = 9

  AMORTISED COST: each element is copied at most once per doubling.
  Over n insertions, total copy work is 1 + 2 + 4 + ... + n = 2n.
  Amortised per insertion: O(1).

  CAPACITY IS ALWAYS A POWER OF 2:
  This is enforced by the constructor. If you pass capacity 10,
  ArrayDeque internally rounds up to 16. This makes the bitwise
  mask trick always work correctly.

Memory Layout Advantage Over LinkedList

MEMORY COMPARISON (100 String elements, 64-bit JVM compressed refs):

  ArrayDeque:
    One Object[] array: 100 × 4 bytes = ~400 bytes for references
    Array object header: 16 bytes
    Total overhead: ~416 bytes

  LinkedList:
    100 × Node objects, each:
      Object header: 16 bytes
      item reference: 4 bytes
      next reference: 4 bytes
      prev reference: 4 bytes
    Per-Node total: ~28 bytes × 100 = ~2800 bytes

  ArrayDeque overhead: ~416 bytes
  LinkedList overhead: ~2800 bytes  (6.7× more)

  CACHE LOCALITY:
    ArrayDeque elements occupy consecutive memory addresses.
    When the CPU loads elements[i], hardware prefetching loads
    elements[i+1], [i+2], etc. into the L1 cache automatically.

    LinkedList node references point to different heap locations.
    Each node.next dereference causes a cache miss if the Node
    was allocated at a different time and lives in a different
    cache line. At high throughput this difference is measurable.

Core Operations with Examples

All Six Safe Methods — Both Ends

Output:
After 5 inserts : [Front, Before-Centre, Centre, After-Centre, Back]
Size            : 5

=== Peek at both ends ===
peekFirst() : Front
peekLast()  : Back
Unchanged   : [Front, Before-Centre, Centre, After-Centre, Back]

=== Poll from both ends ===
pollFirst() : Front
pollLast()  : Back
After polls : [Before-Centre, Centre, After-Centre]

=== Emptying and safe boundary checks ===
isEmpty()   : true
pollFirst() : null
peekLast()  : null
removeFirst(): throws NoSuchElementException

=== contains() — O(n) ===
contains(30) : true
contains(99) : false

ArrayDeque as a Stack — Replacing java.util.Stack

Output:
=== ArrayDeque as LIFO stack ===
Stack (top first)  : [callPaymentGateway(), validatePayment(), processOrder(), main()]
peek()             : callPaymentGateway()

Unwinding call stack:
  returning from: callPaymentGateway()
  returning from: validatePayment()
  returning from: processOrder()
  returning from: main()

=== Postfix expression evaluation ===
  3 4 +                     = 7
  10 2 8 * + 3 -            = 23
  5 1 2 + 4 * + 3 -         = 14

ArrayDeque as a FIFO Queue

Output:
=== ArrayDeque as FIFO queue ===
Queue size     : 4
peek() (head)  : [R001] POST /api/orders

Processing in FIFO order:
  Dispatched: [R001] POST /api/orders
  Dispatched: [R002] GET  /api/products
  Dispatched: [R003] PUT  /api/cart/item
  Dispatched: [R004] DELETE /api/session

Queue empty: true
poll() on empty: null

Iterating ArrayDeque

Output:
for-each (head→tail): Home Products Cart Checkout Confirmation
descendingIterator  : Confirmation Checkout Cart Products Home

Before filter: [88, 32, 75, 14, 91, 56, 44, 100]
After remove(<50): [88, 75, 91, 56, 100]
removeIf(<50)     : [88, 75, 91, 56, 100]

Real-World Example — PhonePe UPI Transaction History Buffer

A UPI payments app displays the last N transactions in the current session without hitting the database on every navigation. New transactions are appended to the tail. When the buffer is full, the oldest transaction is evicted from the head. The user can navigate forward (newest) or backward (oldest) through the window. ArrayDeque's O(1) both-end access handles all four operations.

Output:
--- Recording transactions ---
  RECORDED  : [TXN-001]  Zomato             Rs.  249.00  SUCCESS
  RECORDED  : [TXN-002]  BookMyShow         Rs.  599.00  SUCCESS
  RECORDED  : [TXN-003]  Jio Recharge       Rs.  239.00  SUCCESS
  RECORDED  : [TXN-004]  Amazon             Rs. 1299.00  PENDING
  RECORDED  : [TXN-005]  Swiggy             Rs.  189.00  SUCCESS

==============================================================
  TRANSACTION HISTORY  (last 5)
==============================================================
   1. [TXN-005]  Swiggy             Rs.  189.00  SUCCESS
   2. [TXN-004]  Amazon             Rs. 1299.00  PENDING
   3. [TXN-003]  Jio Recharge       Rs.  239.00  SUCCESS
   4. [TXN-002]  BookMyShow         Rs.  599.00  SUCCESS
   5. [TXN-001]  Zomato             Rs.  249.00  SUCCESS
==============================================================

--- New transaction — buffer full, TXN-001 evicted ---
  EVICTED   : [TXN-001]  Zomato             Rs.  249.00  SUCCESS
  RECORDED  : [TXN-006]  Flipkart           Rs. 2499.00  SUCCESS

==============================================================
  TRANSACTION HISTORY  (last 5)
==============================================================
   1. [TXN-006]  Flipkart           Rs. 2499.00  SUCCESS
   2. [TXN-005]  Swiggy             Rs.  189.00  SUCCESS
   3. [TXN-004]  Amazon             Rs. 1299.00  PENDING
   4. [TXN-003]  Jio Recharge       Rs.  239.00  SUCCESS
   5. [TXN-002]  BookMyShow         Rs.  599.00  SUCCESS
==============================================================

==============================================================
  CHRONOLOGICAL HISTORY  (last 5)
==============================================================
   1. [TXN-002]  BookMyShow         Rs.  599.00  SUCCESS
   2. [TXN-003]  Jio Recharge       Rs.  239.00  SUCCESS
   3. [TXN-004]  Amazon             Rs. 1299.00  PENDING
   4. [TXN-005]  Swiggy             Rs.  189.00  SUCCESS
   5. [TXN-006]  Flipkart           Rs. 2499.00  SUCCESS
==============================================================

--- Quick access ---
Latest : [TXN-006]  Flipkart           Rs. 2499.00  SUCCESS
Oldest : [TXN-002]  BookMyShow         Rs.  599.00  SUCCESS

Performance Considerations

Stack.removeLast is O(n): java.util.Stack inherits Vector's structure — there is no tail pointer. Removing the last element requires traversal. ArrayDeque.removeLast() is O(1) via the tail index. This is a genuine asymptotic difference, not just a constant-factor improvement.

Resize is O(n) amortised: Each element is copied at most once per doubling cycle. Over n insertions, total copy work across all resizes is bounded by 2n. The amortised cost per insertion is O(1). This is the same guarantee that makes ArrayList append O(1) amortised.

Thread safety: ArrayDeque is not thread-safe. For concurrent producer-consumer with both-ends access, use LinkedBlockingDeque from java.util.concurrent. For single-producer single-consumer FIFO, ArrayBlockingQueue is more memory-efficient.

Best Practices

Declare the variable as Deque<E> for both-ends use, Queue<E> for FIFO-only use. Deque<String> history = new ArrayDeque<>() exposes the full both-ends API. Queue<String> tasks = new ArrayDeque<>() restricts callers to FIFO semantics only, which prevents accidental use of addFirst() when the intent is FIFO. Choose the narrowest interface that matches the actual access pattern.

Pre-size ArrayDeque when the expected number of elements is known. new ArrayDeque<>(expectedSize) allocates a backing array large enough to hold expectedSize elements without triggering any resize. The internal capacity is rounded up to the next power of 2. This eliminates O(n) resize operations and the temporary double-allocation during growth for bulk-loaded deques.

Use push()/pop()/peek() for stack semantics, offer()/poll() for queue semantics. The naming signals intent to readers. A method that uses push and pop reads as a stack. A method that uses offer and poll reads as a queue. Mixing them in one method (e.g., push to enqueue and pollLast to dequeue from the wrong end) produces correct but confusing code that is hard to maintain.

Clear slots after removal — ArrayDeque already does this for you. When pollFirst() or pollLast() removes an element, ArrayDeque nulls the vacated array slot. This is essential for garbage collection — if the slot were not cleared, the Object[] would hold a strong reference to the removed element even though logically it has been removed. This is handled internally and is one reason ArrayDeque is preferred over manually managed circular arrays.

Common Mistakes

Mistake 1 — Inserting null Into ArrayDeque

Mistake 2 — Using java.util.Stack in New Code

Mistake 3 — Confusing Iteration Order With Priority Order

Output:
for-each: [30, 10, 50, 20]
PriorityQueue poll: 10 20 30 50

Mistake 4 — Using LinkedList When ArrayDeque Handles the Use Case

Interview Questions

Q1. What is ArrayDeque in Java and what are its main advantages over LinkedList and Stack?

ArrayDeque<E> is a concrete Deque implementation backed by a resizable circular array. Every operation at both ends is O(1) amortised. Compared to LinkedList: no per-element Node allocation means less GC pressure, and the contiguous array layout gives better CPU cache performance. Compared to java.util.Stack: Stack extends Vector, which synchronises every push(), pop(), and peek() call even in single-threaded code — pure overhead. ArrayDeque has no synchronisation. The Java documentation explicitly recommends ArrayDeque as the preferred replacement for both.

Q2. How does ArrayDeque implement O(1) operations at both ends?

ArrayDeque maintains two integer indices — head (the front element) and tail (the next insertion slot at the back) — into a circular Object[] array. addFirst(e) decrements head using bitwise wrap: head = (head - 1) & (capacity - 1), then writes elements[head] = e. addLast(e) writes elements[tail] = e, then increments tail. pollFirst() reads elements[head], nulls the slot, and increments head. All are direct array index operations — O(1). Resize happens when the array is full: a new array of double capacity is allocated, elements are copied in logical order, and head is reset to 0. This is O(n) but amortised O(1) over n insertions.

Q3. Why is the capacity of ArrayDeque always a power of 2?

The circular wrap-around uses bitwise AND masking: nextIndex = (index + 1) & (capacity - 1). This only produces correct wrap-around results when capacity - 1 is all-ones in binary — which happens precisely when capacity is a power of 2. For example, capacity 16 gives mask 15 (binary 1111). (15 + 1) & 15 = 16 & 15 = 0 — correctly wraps to the start. Bitwise AND is faster than modulo division, which is why Java enforces power-of-2 capacities internally. If you pass capacity 10 to the constructor, ArrayDeque rounds up to 16.

Q4. What is the difference between the throwing and null-returning method groups in ArrayDeque?

Every operation exists in two forms. The throwing group — addFirst, removeFirst, getFirst (and equivalents for last) — throws NoSuchElementException when the deque is empty, or IllegalStateException when capacity is exceeded (for bounded implementations). The null-returning group — offerFirst, pollFirst, peekFirst — returns null or false instead. For ArrayDeque, which is unbounded, capacity overflow never occurs, so the only practical difference is empty-deque behaviour. Production code should use the null-returning group for routine processing loops and reserve the throwing group for situations where an empty deque is a genuine programming error.

Q5. Can ArrayDeque be used as both a stack and a queue on the same object?

Yes — this is one of ArrayDeque's most useful properties. Both access patterns use opposite ends of the same circular buffer. Stack operations (push/pop) operate on the head. Queue operations (offer/poll) add to the tail and remove from the head. A sliding window buffer uses offerLast for new arrivals and pollFirst for eviction. All three patterns can coexist in the same ArrayDeque object without conflict, as long as the caller is consistent about which end represents the "front" for each semantic.

Q6. Why does ArrayDeque prohibit null elements?

pollFirst() and pollLast() return null to signal that the deque is empty — there is no separate isEmpty() check required before polling. If null elements were stored, a null return from poll would be ambiguous: it could mean "the deque was empty" or "the front element was null." Prohibiting null removes that ambiguity entirely. LinkedList allows null elements because it uses size > 0 as its emptiness signal rather than relying on the returned value. If a null-value sentinel is genuinely needed, use Optional<E> as the element type.

FAQs

What is the initial capacity of ArrayDeque and how does it grow?

The default internal capacity is 16 elements. The constructor new ArrayDeque<>(n) pre-allocates an array large enough for n elements, rounded up to the next power of 2. When the array becomes full, ArrayDeque allocates a new array of approximately double the capacity, copies all elements in logical order (head to tail), and resets head to 0. Growth is always to the next power of 2 to maintain the bitwise-mask wrap-around property.

Is ArrayDeque the same as a circular buffer?

Functionally yes. A circular buffer is any fixed-size buffer where reads and writes wrap around from the end back to the beginning. ArrayDeque uses exactly this structure with resizing on top. The key practical difference: a true fixed-size circular buffer has a maximum capacity and overwrites or rejects new elements when full. ArrayDeque never rejects elements — it resizes instead. For a true fixed-capacity circular buffer that overwrites old data, you would need to implement the eviction policy manually using ArrayDeque with a size guard, as shown in the real-world example above.

When should I use ArrayDeque over PriorityQueue?

Use ArrayDeque when processing order is either FIFO (arrival order) or LIFO (most-recently-added first). Use PriorityQueue when processing order depends on element value or priority — the smallest (or custom-highest-priority) element should always be processed next. ArrayDeque provides O(1) both-ends access; PriorityQueue provides O(log n) poll() and O(1) peek(). If your task queue needs priority-based dispatch, PriorityQueue is the right choice. If tasks should be processed in the order they arrived, ArrayDeque is faster.

Can ArrayDeque be iterated safely while removing elements?

Removing elements during for-each iteration throws ConcurrentModificationException — same as ArrayList and HashSet. Use iterator().remove() or removeIf(predicate) for safe removal during traversal. Both maintain modCount consistency internally. removeIf() is the cleaner Java 8+ choice for predicate-based removal and handles the bookkeeping transparently.

How does ArrayDeque compare to ArrayBlockingQueue for queue use?

Both use array-backed circular buffers, but for different scenarios. ArrayDeque is single-threaded, unbounded (grows as needed), and O(1) amortised. ArrayBlockingQueue is thread-safe, bounded (fixed capacity at construction), and uses a ReentrantLock for thread safety. ArrayBlockingQueue.put() blocks when full, take() blocks when empty — ideal for bounded producer-consumer pipelines. ArrayDeque is the choice for single-threaded workloads; ArrayBlockingQueue for concurrent ones.

Does ArrayDeque support random access by index?

No. ArrayDeque implements Deque not List, so there is no get(int index) method. It does not expose the internal array index — only the head and tail operations are public. If index-based access alongside deque operations is needed, LinkedList is the only standard Deque implementation that also implements List. For most cases where you think you need index access on a deque, you likely need either an ArrayList or a different design.

Summary

ArrayDeque<E> is the practical workhorse behind most Java stack and queue patterns. Its circular resizable array gives O(1) amortised operations at both ends with no per-element allocation overhead, no synchronisation cost, and cache-friendly sequential memory. The Java documentation recommends it explicitly over java.util.Stack and java.util.LinkedList for all non-concurrent queue and stack use cases.

Two implementation details that matter for interviews: capacity is always a power of 2 so the bitwise-AND wrap-around works correctly, and null elements are prohibited because poll() uses null as the "empty deque" signal. Both are design decisions made deliberately for performance and correctness.

Declare the variable as Deque<E> for both-ends code, Queue<E> for FIFO-only code. Pre-size when the expected element count is known. Never insert null. And when you review a PR that uses new Stack<>(), you now have the exact technical argument for why new ArrayDeque<>() is the right replacement.

What to Read Next