skip to content

How does LinkedList implement the Deque and Queue interfaces, and why might you still prefer ArrayDeque?

level: seniorimportance: should knowfreq 58%

answer

  1. LinkedList implements List + Deque (Deque extends Queue)
  2. first/last pointers => O(1) at both ends => queue/stack/deque
  3. ArrayDeque = circular array, less memory, better cache
  4. Prefer ArrayDeque over LinkedList AND over legacy Stack
  5. Keep LinkedList for List API + Deque, or nulls

basics

~20 s

LinkedList implements Deque (a double-ended queue) and Queue, so it offers addFirst/addLast/peek/poll in O(1) and can act as a stack, queue, or deque. But ArrayDeque is usually faster and lighter, so it is the preferred choice.

solid answer

~50 s

LinkedList implements both Queue and Deque. Because it keeps first and last pointers, the end operations — addFirst, addLast, offerFirst/offerLast, peekFirst/peekLast, pollFirst/pollLast — run in O(1), so a LinkedList can serve as a FIFO queue, a LIFO stack, or a general double-ended queue. However, for these roles ArrayDeque is usually the better implementation: it is backed by a resizable circular array, so it has far less per-element memory overhead (no node object holding the element plus prev and next references), much better cache locality, and fewer allocations and less GC pressure. ArrayDeque's Javadoc calls it likely to be faster than Stack as a stack and than LinkedList as a queue. The usual reasons to keep LinkedList are needing the full List API alongside Deque, or having to store null elements, which ArrayDeque forbids and Deque's Javadoc discourages because poll and peek return null on an empty deque.

go deeper

for a junior

Knows LinkedList can be used as a queue or stack and offers add/remove at both ends.

for a middle

Names the Queue/Deque methods (offer/poll/peek, addFirst/addLast) and knows they are O(1), and that ArrayDeque exists as an alternative.

for a senior

Explains the circular-array vs node trade-off (memory, cache, GC), recommends ArrayDeque, and cites the null and full-List-API exceptions for keeping LinkedList.

for a principal

Sets defaults across a codebase (ArrayDeque for stack/queue, concurrent queues for threading), and can justify the rare LinkedList exception with measured evidence.

## Background: Queue and Deque - A **Queue** is a collection you typically process in FIFO (first-in-first-out) order — add at the back, remove from the front (like a checkout line). The `java.util.Queue` interface adds methods such as `offer` (add to tail), `poll` (remove head, returns null if empty), and `peek` (look at head). - A **Deque** ('deck', double-ended queue) lets you add and remove at *both* ends. The `java.util.Deque` interface adds `addFirst/addLast`, `offerFirst/offerLast`, `pollFirst/pollLast`, `peekFirst/peekLast`, plus stack methods `push`/`pop`. A Deque can therefore act as a FIFO queue *or* a LIFO stack (last-in-first-out). ## How LinkedList fills these roles `java.util.LinkedList implements List, Deque` (and Deque extends Queue). Because LinkedList is a doubly-linked list holding direct `first` and `last` pointers, operating on either end is **O(1)** — you only relink a couple of node references and move a pointer. That makes it a natural Deque: - **As a FIFO queue:** `offer(e)` adds to the tail, `poll()` removes the head. - **As a LIFO stack:** `push(e)` adds to the head, `pop()` removes the head. - **As a deque:** use the `*First`/`*Last` methods directly. All of these are O(1). For LIFO use they also stand in for the legacy synchronized `Stack` class, which extends `Vector`; its Javadoc says the `Deque` interface and its implementations should be used in preference to it. ## Why ArrayDeque is usually better `ArrayDeque` also implements `Deque`, but it is backed by a **resizable circular array** instead of nodes. A circular array uses two indices (head and tail) that wrap around the array modulo its length, so both ends are O(1) amortized: an end operation shifts no elements, and copies the array only when it has to grow. Compared to LinkedList: - **Memory:** no per-element node objects. LinkedList allocates a heap node (header + value reference + prev + next) for *every* element; ArrayDeque stores bare references packed in one array. Far less overhead while the array is reasonably full; it never shrinks on its own, so a drained deque keeps its capacity. - **Cache locality:** the array is contiguous, so traversal and end operations are cache-friendly; LinkedList's nodes can scatter on the heap, which causes cache misses. - **Allocation / GC:** ArrayDeque allocates rarely (only on resize); LinkedList allocates a node per add and creates garbage per remove, raising GC pressure. ArrayDeque's Javadoc states the result at its own strength: the class is "likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue." `Stack`'s Javadoc shows `new ArrayDeque<Integer>()` as its replacement. ## When LinkedList still wins - You need the **full List API** (indexed `get`/`set`, `ListIterator` with positional add/remove) *and* deque behavior in one object. ArrayDeque is not a List. - You must store **null** elements. ArrayDeque prohibits null (it uses null internally as an empty-slot sentinel), whereas LinkedList allows null. `Deque`'s Javadoc still strongly encourages users *not* to insert nulls, because `poll` and `peek` also return null on an empty deque: on a LinkedList that may hold a null, a null return no longer proves it is empty. - You need a `ListIterator` that can insert/remove at an interior position in O(1) while traversing. ## Since JDK 21: the sequenced methods `List` and `Deque` both extend `SequencedCollection`, added in JDK 21, so `ArrayList` also has `getFirst`, `addFirst`, `removeLast` and the rest, and `LinkedList` has `reversed()`. Wanting those names is no reason to pick LinkedList, though `ArrayList` is not a `Deque`, and its `addFirst` and `removeFirst` shift elements, which is O(n). ## Key terms - **FIFO / LIFO:** first-in-first-out (queue) / last-in-first-out (stack). - **Circular array:** an array used with wrap-around head/tail indices so both ends are cheap. - **Sentinel:** a reserved value (here, null) used to mark empty slots — one reason ArrayDeque bans null, alongside `poll` and `peek` using null to signal an empty deque. - **GC pressure:** the rate of garbage creation that forces the garbage collector to run more often. ## Takeaway LinkedList *can* be a queue/stack/deque in O(1) at both ends because it is doubly-linked with end pointers. But ArrayDeque does the same job with less memory, better cache behavior, and less GC — so prefer ArrayDeque unless you need List methods alongside deque ops or must store nulls.

  • Why does ArrayDeque forbid null elements while LinkedList allows them?
    ArrayDeque's source keeps every cell not holding an element null, and its insert methods throw NullPointerException on a null element. LinkedList wraps each value in a node, so it can store null, but the ambiguity does not vanish: its poll and peek also return null when it is empty, so a null return can mean either. Deque's Javadoc strongly encourages users not to insert nulls for that reason.
  • If you need a thread-safe queue, is LinkedList the right choice?
    No. LinkedList is not synchronized. For concurrency use a dedicated implementation such as ConcurrentLinkedQueue (non-blocking FIFO), LinkedBlockingQueue / ArrayBlockingQueue (blocking producer-consumer), or ConcurrentLinkedDeque, rather than wrapping a LinkedList.

LinkedList as a deque is a train where you can hook/unhook cars at either end. ArrayDeque is a rotating carousel of fixed seats — same add/remove-at-both-ends ability, but no separate car (node) allocated per passenger, so it is lighter and faster.

  • Recommending LinkedList as the default queue/stack today — ArrayDeque is preferred
  • Saying ArrayDeque can store null
  • Claiming LinkedList is thread-safe or synchronized
  • Forgetting that Deque extends Queue, so a Deque is also a Queue
  • Using the legacy Stack class instead of ArrayDeque/Deque for LIFO

Deque interface
Java 1.6
Queue interface
Java 1.5
ArrayDeque
Java 1.6

Assumes JDK 27. List and Deque have both extended SequencedCollection since JDK 21, and LinkedList, ArrayDeque and Deque read the same on JDK 25 LTS.

context