How does LinkedList implement the Deque and Queue interfaces, and why might you still prefer ArrayDeque?
answer
- LinkedList implements List + Deque (Deque extends Queue)
- first/last pointers => O(1) at both ends => queue/stack/deque
- ArrayDeque = circular array, less memory, better cache
- Prefer ArrayDeque over LinkedList AND over legacy Stack
- Keep LinkedList only for List API + nulls
basics
~20 sLinkedList 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
~40 sLinkedList implements both Queue and Deque. Because it keeps first and last pointers, all the deque 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. That is why the Queue/Deque tutorials historically used it. However, for these roles ArrayDeque is almost always the better implementation: it is backed by a resizable circular array, so it has far less per-element memory overhead (no node objects with two references each), much better cache locality, and fewer allocations and less GC pressure. ArrayDeque is the recommended Deque/stack/queue today; the only reasons to keep LinkedList are needing the full List API alongside Deque, or needing to store null elements (ArrayDeque forbids null).
go deeper
Knows LinkedList can be used as a queue or stack and offers add/remove at both ends.
Names the Queue/Deque methods (offer/poll/peek, addFirst/addLast) and knows they are O(1), and that ArrayDeque exists as an alternative.
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.
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), which is why older Java tutorials reached for LinkedList to demonstrate queues and stacks. (It replaced the legacy synchronized `Stack` class, which extends `Vector` and is discouraged.) ## 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 without ever shifting elements. 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. - **Cache locality:** the array is contiguous, so traversal and end operations are cache-friendly; LinkedList's scattered nodes cause cache misses. - **Allocation / GC:** ArrayDeque allocates rarely (only on resize); LinkedList allocates a node per add and creates garbage per remove, raising GC pressure. For these reasons the JDK documentation explicitly recommends ArrayDeque over both Stack (for LIFO) and LinkedList (for FIFO). ## 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. - You need a `ListIterator` that can insert/remove at an interior position in O(1) while traversing. ## Key terms - **FIFO / LIFO:** first-in-first-out (queue) / last-in-first-out (stack). - **Circular array:** a fixed array used with wrap-around head/tail indices so both ends are cheap. - **Sentinel:** a reserved value (here, null) used to mark empty slots — the reason ArrayDeque bans null. - **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 uses null internally as a sentinel to mark empty slots in its backing array, so an inserted null would be indistinguishable from an empty slot and would break methods like poll/peek. LinkedList stores each value in its own node, so null is just a normal value with no ambiguity.
- 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 (lock-free 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.
saying these in an interview costs you the question
- 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