skip to content

When implementing a FIFO queue, why is ArrayDeque generally preferred over LinkedList?

level: seniorimportance: should knowfreq 45%

answer

  1. ArrayDeque = contiguous circular array -> cache-friendly, low overhead
  2. LinkedList = per-element Node with prev/next -> ~2-3x memory, pointer chasing, 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 only for List semantics or null storage

basics

~20 s

ArrayDeque stores elements in a contiguous array, so it is faster and uses less memory than LinkedList, which wraps every element in a node with two pointers. For a plain queue, ArrayDeque is the better default.

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: elements sit contiguously in memory, giving excellent cache locality, and offer/poll are amortized O(1) at both ends with low per-element overhead. LinkedList is a doubly linked list: every element is boxed in a Node object holding the value plus prev/next references, which roughly triples memory per element and scatters nodes across the heap, hurting cache performance and adding GC pressure. The JDK Javadoc explicitly notes ArrayDeque is likely faster than LinkedList when used as a queue. You'd choose LinkedList only when you specifically need List behavior too (positional access, ListIterator with insertion in the middle) or genuinely need to 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)

// Only when you also need List semantics or null storage:
Deque<String> withNulls = new LinkedList<>();
withNulls.offer(null);  // allowed in LinkedList; would throw 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 doubles in size (a rare O(n) copy that amortizes to O(1) per operation). Key properties: - Elements are **contiguous** in memory -> excellent **cache locality** (the CPU prefetches neighboring elements). - **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 **two pointers** (~2-3x the memory of an array slot, plus object header). - Nodes are scattered across the heap -> **poor cache locality** (pointer chasing, frequent cache misses). - 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; far smaller footprint. - **Speed**: contiguous access and prefetching make iteration and end-operations measurably faster in practice; less GC churn. 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` only 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`). 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` only 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), roughly 2-3x the memory of a bare array slot, and the nodes are scattered on the heap causing cache misses and GC pressure.
  • 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.

saying these in an interview costs you the question

  • Claiming LinkedList is faster for queues because 'no resizing' (locality usually dominates)
  • 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

context

resolving links…