ArrayDeque vs LinkedList as Queue/Stack
Fast recall
Quick revision
Core answer
Knowledge of Deque implementations, memory layout, and why the legacy Stack class is deprecated in practice
Using java.util.Stack (synchronized, slow) or LinkedList without understanding the memory overhead of node objects
Mention that ArrayDeque uses a circular array with head and tail pointers, avoids null elements, and has better cache performance. Also note that java.util.Stack is considered legacy and Deque is the recommended replacement per Java docs.
Interview-ready guide
Interview answer
ArrayDeque is the right default for both stack and queue patterns — it beats Stack on performance and LinkedList on memory efficiency.
ArrayDeque:
- Circular array with head/tail pointers — O(1) amortized at both ends, no element shifting
- Contiguous storage: CPU cache line loads multiple elements per fetch; dramatically faster iteration
- Does not allow null — uses null internally as a sentinel for empty slots
LinkedList problems:
- ~40 bytes per element, heap-scattered Node objects — cache miss on virtually every access
- Only remaining advantage: O(1) mid-list insert/delete at a position held by a ListIterator (rare in practice)
java.util.Stack problems:
- Extends Vector, which synchronizes every method — unnecessary overhead for single-threaded use
- The Javadoc itself recommends ArrayDeque as the replacement
I recommend ArrayDeque as the default for all stack and queue patterns. LinkedList's only remaining niche is holding a ListIterator at a known position with many local inserts — which almost never happens in practice.
ArrayDeque vs LinkedList as Queue/Stack
Direct Answer
ArrayDeque uses a circular resizable array — no per-element node allocation, better CPU cache locality, and lower GC pressure. LinkedList allocates a Node object per element (~40 bytes overhead). For both stack and queue patterns, ArrayDeque is faster and more memory-efficient in practice.
Deep Dive & Architecture
compute, merge, computeIfAbsent, and computeIfPresent are Map methods (Java 8+) that atomically combine get + check + put into a single operation, replacing the verbose get-check-put anti-pattern. computeIfAbsent(key, mappingFunction) — if key absent, compute value and put; most-used for lazy initialization of multi-valued maps: map.computeIfAbsent(key, k -> new ArrayList<>()).add(value). computeIfPresent(key, remappingFunction) — if key present, recompute value (or remove if null returned). compute(key, remappingFunction) — recompute regardless of presence (function gets old value or null). merge(key, value, remappingFunction) — if absent, put value; if present, apply function to combine: map.merge(word, 1, Integer::sum) is the idiomatic word-counter. Why they matter: (1) atomic in ConcurrentHashMap — no lost updates from concurrent get-check-put races; (2) less code than if (map.containsKey(k)) map.put(k, ...) else map.put(k, ...); (3) cleaner intent — the operation says what it does. Pitfalls: (1) not atomic in non-concurrent maps (HashMap) — only the API is single-call, not thread-safe; (2) returning null from a remapping function removes the key — surprising; (3) don't recursively modify the map inside the function — undefined behavior; (4) merge doesn't handle null values the same way as compute — read the Javadoc. For interviews: lead with 'replaces get-check-put, atomic in ConcurrentHashMap, idiomatic for multimap lazy-init and counters'.
ArrayDeque uses a circular resizable array — no per-element node allocation, better CPU cache locality, and lower GC pressure. LinkedList allocates a Node object per element (~40 bytes overhead). For both stack and queue patterns, ArrayDeque is faster and more memory-efficient in practice.
A common mistake is confusing the interface with the implementation (e.g., saying List when you mean ArrayList), or not knowing that Map does not extend Collection.
Common Mistakes & Pitfalls
Using java.util.Stack (synchronized, slow) or LinkedList without understanding the memory overhead of node objects
Check your understanding
Answer these without looking back at the article.
- What is the Java Collections Framework (JCF) and why does it exist? It provides a unified architecture of interfaces and implementations for storing and manipulating groups of objects, replacing the ad-hoc pre-JCF classes (Vector, Hashtable, Enumeration) with a consistent, interoperable API.
- How does HashSet work internally in Java?
- How does HashMap internally handle hash collisions in Java 8+? Explain the transition from linked list to tree.
Related interview prep categories
1Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.