skip to content

What is ArrayDeque, how does it store elements, and why is it generally preferred over LinkedList for a FIFO queue?

level: seniorimportance: should knowfreq 45%

answer

  1. ArrayDeque = contiguous circular array -> cache-friendly, low overhead
  2. LinkedList = one Node per element, GC pressure
  3. Same big-O at the ends, but ArrayDeque wins constants + memory
  4. JDK Javadoc: ArrayDeque likely faster than LinkedList as a queue
  5. Pick LinkedList for List semantics or null storage

basics

~20 s

ArrayDeque is a resizable circular-array Deque. Holding references in one array, it is likely faster and lighter than LinkedList, which wraps every element in a two-pointer node, so it is the better default for a plain queue.

solid answer

~50 s

Both ArrayDeque and LinkedList implement Deque and can serve as FIFO queues, but ArrayDeque is the better default. ArrayDeque is a resizable circular array: element references sit contiguously in one array, which is cache-friendly to walk, and offer/poll are amortized O(1) at both ends with no allocation per element. LinkedList is a doubly linked list: every element gets a Node object holding the value plus prev/next references, 24 bytes with compressed references at JDK 27 and 25 against a 4-byte array slot plus spare capacity, and nodes can scatter across the heap, adding GC work. The JDK Javadoc explicitly notes ArrayDeque is likely faster than LinkedList when used as a queue. You'd choose LinkedList mainly when you need List behavior too (positional access, ListIterator with insertion in the middle) or must store null elements, since ArrayDeque forbids null. For a pure queue or stack, reach for ArrayDeque.

code

java · 8 lines
java
// Preferred default for a FIFO queue
Queue<Task> q = new ArrayDeque<>();
q.offer(t1);            // tail, amortized O(1)
Task next = q.poll();   // head, O(1)

// When you also need List semantics or null storage:
Deque<String> withNulls = new LinkedList<>();
withNulls.offer(null);  // allowed in LinkedList, though Queue's Javadoc advises against it; NPE in ArrayDeque

go deeper

for a junior

Knows ArrayDeque is the recommended default for queues and that LinkedList uses more memory.

for a middle

Explains the array-vs-node storage difference and that both are O(1) at the ends but ArrayDeque has better constants and memory.

for a senior

Quantifies the overhead (node objects, pointers, cache misses, GC), cites the JDK recommendation, and names the precise cases where LinkedList is justified (List semantics, null).

for a principal

Reasons about cache locality and allocation behavior at scale, the amortized-resize tradeoff, and chooses the right concurrent/bounded structure when the requirement moves beyond a single-threaded unbounded queue.

## The setup Both `ArrayDeque` and `LinkedList` implement the `Deque` interface, so either can be used as a FIFO queue (`offer`/`poll`/`peek`). The question is which to pick by default. The short answer: **`ArrayDeque`**, with `LinkedList` reserved for specific needs. ## How each stores data ### ArrayDeque — resizable circular array `ArrayDeque` keeps elements in a single backing array with two indices, `head` and `tail`, that wrap around (modulo the array length). Inserting at the tail or removing from the head just adjusts an index; when the array fills, it grows, at JDK 27 as at 25 to `2n + 2` slots below length 64 and `1.5n` from there (a rare O(n) copy that amortizes to O(1) per operation). Key properties: - Element **references** are **contiguous** in memory -> good **cache locality** when walking the array. The element objects themselves live elsewhere on the heap, in either class. - **Low overhead** per element: just the reference in the array slot. - Amortized **O(1)** add/remove at both ends. ### LinkedList — doubly linked list `LinkedList` stores each element in a separate **`Node`** object containing the element reference plus a `prev` and a `next` pointer. Properties: - Each element costs an extra object with an **object header and three references** (`item`, `prev`, `next`). With compressed references, on by default when the maximum heap is small enough, 1,000,000 `offer` calls measured 24,000,000 bytes of `LinkedList$Node` at both JDK 27.0.1 and 25.0.3, against about 5,000,000 bytes of array for a default `ArrayDeque` and 4,000,000 when presized. Without them (`-Xmx40g`) a node is 32 bytes at 27.0.1, where compact object headers are the default, and 40 at 25.0.3, and an array slot is 8. - Nodes are separate objects that can scatter across the heap -> **weaker cache locality** (pointer chasing). - Adding/removing at the ends is O(1), but the constant factor and memory traffic are higher, and it creates more garbage for the GC. ## Why ArrayDeque usually wins For queue/stack workloads (add/remove only at the ends), the operations have the same big-O, but ArrayDeque wins on: - **Memory**: no per-element node objects; a far smaller structure, although the array never shrinks once grown. - **Speed**: no allocation per element and less pointer chasing, so less GC churn. The Javadoc's word is "likely", so measure when it matters. The JDK's own Javadoc states `ArrayDeque` is **likely to be faster than `LinkedList` when used as a queue** (and faster than `Stack` when used as a stack). ## When LinkedList still makes sense Reach for `LinkedList` when you need something ArrayDeque can't give: 1. **List + Deque together**: you need positional access (`get(int)`, `add(int, e)`) or a `ListIterator` that inserts/removes in the **middle** in O(1) given an iterator position. (Note: locating an arbitrary index in a LinkedList is still O(n).) 2. **Null elements**: `LinkedList` permits `null`; `ArrayDeque` forbids it (null collides with the null-means-empty signal of `poll`/`peek`). It is a real difference, but `Queue`'s Javadoc advises against inserting null even where it is permitted. 3. **No costly resize spikes matter**: LinkedList never does a big array copy, but this rarely outweighs its overhead. ## Caveats common to both - Neither is thread-safe; use `java.util.concurrent` structures (`ConcurrentLinkedQueue`, `ArrayBlockingQueue`, `LinkedBlockingQueue`) for concurrency. - For a *bounded* queue with back-pressure, neither plain class enforces capacity; use a bounded `BlockingQueue`. ## Bottom line Default to **`ArrayDeque`** for queues and stacks. Choose `LinkedList` when you specifically need List semantics or null storage.

  • What concrete cost does each LinkedList element carry that an ArrayDeque slot does not?
    Each LinkedList element is wrapped in a separate Node object holding the value plus prev and next references and an object header. With compressed references that is 24 bytes at JDK 27 and 25, against 4 for a bare array slot before spare capacity; without them it is 32 at 27 or 40 at 25, against 8. It also means one allocation per element and pointer chasing.
  • Name one situation where LinkedList is the right choice over ArrayDeque.
    When you need List behavior alongside Deque (e.g. ListIterator-based middle insertion/removal) or must store null elements, since ArrayDeque forbids null.

  • Claiming LinkedList is faster for queues because 'no resizing' (ArrayDeque's Javadoc says the reverse is likely)
  • Saying ArrayDeque allows null like LinkedList
  • Asserting LinkedList gives O(1) access at an arbitrary index (it's O(n) to find it)
  • Treating either as thread-safe

java.util.ArrayDeque
Java 1.6

Assumes JDK 27. The growth numbers come from private code rather than the API contract and are the same at JDK 25. The byte counts assume compressed references, where a node is 24 bytes at both; without them it is 32 at JDK 27, where compact object headers are the default, and 40 at JDK 25.

context