Java ArrayDeque vs LinkedList: Choosing the Right Deque
Compare Java's ArrayDeque and LinkedList for stacks, queues, and double-ended queues: structural differences, performance, memory, null handling, and how to choose.

When you need a double-ended queue in Java, the java.util.Deque interface has two common implementations: ArrayDeque and LinkedList. Both support adding and removing elements at both ends, but their underlying data structures lead to different performance characteristics, memory footprints, and usage constraints. For most stack and queue use cases, ArrayDeque is the better default. Choose LinkedList when you also need List behavior, indexed access, or null element support.
Structural Differences That Affect Behavior
ArrayDeque uses a resizable circular array to store elements. It grows automatically when capacity is exceeded, similar to ArrayList. Because it is array-based, elements are stored contiguously in memory, which improves cache locality when iterating or accessing consecutive elements.
LinkedList implements Deque (and List) using a doubly-linked list. Each element is wrapped in a node that holds references to the previous and next nodes. This means elements are scattered across memory, and each node carries two extra references plus object header overhead.
These structural differences have direct consequences:
- Memory overhead per element:
LinkedListuses more memory per element because of the node metadata.ArrayDequestores only the elements, plus some unused capacity due to its power-of-two sizing. - Cache behavior:
ArrayDequebenefits from spatial locality;LinkedListcauses more cache misses when traversing. - Element retrieval by index:
LinkedListsupports index-based access viaget(int), but it must traverse from the beginning or end.ArrayDequedoes not support indexed access; it only provides access to the ends.
Performance: Where Each Shines
For queue and stack operations (addFirst, removeFirst, addLast, removeLast, peek), both provide O(1) amortized time. The constant factors differ.
ArrayDequeis generally faster for these operations because it avoids allocating a new node for each element; it only updates array slots. Adding at the end may occasionally trigger a resize, but the amortized cost stays O(1).LinkedListmust allocate a new node for every insertion and dereference node references on removal. This allocation overhead and indirection make the constant factor larger.
However, LinkedList can be a better choice when you frequently insert or remove elements in the middle of a list, since it can splice nodes in O(1) given a specific node reference. But note: to reach that node, you still need to traverse, unless you keep a reference to an existing node. In practice, this advantage is rarely decisive unless the application holds such references and performs many mid-list modifications.
Iteration Performance and Memory Footprint
Iterating over a Deque is a common operation, and the difference can be substantial.
// Iterating with ArrayDeque
ArrayDeque<String> deque = new ArrayDeque<>();
// ... add elements ...
for (String item : deque) {
System.out.println(item);
}// Iterating with LinkedList
LinkedList<String> list = new LinkedList<>();
// ... add elements ...
for (String item : list) {
System.out.println(item);
}The ArrayDeque iterator accesses contiguous array memory, so the CPU can prefetch future elements efficiently. The LinkedList iterator follows node references, which are scattered across the heap, causing memory cache misses. For large collections, this can make a measurable difference in throughput.
Memory usage also diverges significantly. A LinkedList with one million elements can use many megabytes more than an ArrayDeque with the same number of elements, due to node overhead. The ArrayDeque may waste some capacity if it grows to the next power of two, but that wasted space is typically far less than the per-node overhead of the linked list.
The null Element Constraint
One pragmatic difference is that ArrayDeque does not allow null elements. Attempting to add a null throws NullPointerException. LinkedList, on the other hand, permits null elements. This can be a deciding factor if your data model includes null as a valid value.
ArrayDeque<String> deque = new ArrayDeque<>();
deque.addLast(null); // Throws NullPointerException
LinkedList<String> list = new LinkedList<>();
list.addLast(null); // AllowedIf you rely on null sentinel values, LinkedList is the only one of the two that supports it. If null is not part of your domain, ArrayDeque avoids accidental null propagation and enforces non-null constraints at the boundary.
Which One to Use for Queues and Stacks
For standard queue or stack usage—where you operate only at the ends—ArrayDeque is the recommended choice in most cases. The ArrayDeque Javadoc notes that it is likely to be faster than Stack when used as a stack and faster than LinkedList when used as a queue. Here's a concrete example of implementing a simple stack with ArrayDeque:
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
int top = stack.pop(); // Returns 2When you need a FIFO queue, ArrayDeque also works seamlessly:
Deque<String> queue = new ArrayDeque<>();
queue.offerLast("first");
queue.offerLast("second");
String head = queue.pollFirst(); // Returns "first"The same code using LinkedList would work, but with the extra memory and allocation overhead for no functional benefit in this scenario.
When LinkedList Actually Makes Sense
LinkedList is not universally inferior. It becomes a rational choice when you need:
- A list-like interface with indexed access (
get(int),set(int, E)) in addition to deque operations.ArrayDequelacks these methods. - Insertion/removal at arbitrary positions when you already have a reference to a node, or when the list is short and you need to iterate back and forth. For small lists, the constant factors are negligible.
nullelement support if your domain requires it.- A combination of
ListandDequein one object, avoiding the need to maintain two separate collections.
For example, a small LRU cache might use a LinkedList to maintain recency order with O(1) removal from the head and tail, while still being able to iterate over the list. However, for large data sets, consider more specialized structures like LinkedHashMap instead of relying on LinkedList for LRU behavior.
Handling Concurrency
In the realm of concurrency, neither ArrayDeque nor LinkedList is thread-safe. If you need a thread-safe deque, you're better off using ConcurrentLinkedDeque or wrapping a Deque with Collections.synchronizedDeque.
Given that both are unsynchronized, the performance comparison remains relevant in single-threaded scenarios or when external synchronization is already in place. When you have concurrent access, the choice of ArrayDeque vs LinkedList becomes a minor detail compared to selecting the right concurrent collection.
Choosing in Practice
For virtually any new code that needs a stack, queue, or double-ended queue without index access, start with ArrayDeque. It delivers better performance and lower memory usage. Only fall back to LinkedList when you genuinely need its List features, indexed access, or null element support.
If you find yourself using LinkedList for its deque capabilities, ask whether you actually need the List interface. If not, switching to ArrayDeque can reduce memory consumption and improve iteration speed without changing the rest of your code.
Try matching browser tools
All toolsSmall utilities that fit Java work — they run entirely in this browser tab, so nothing you paste leaves your device.
Related Java guides
All Java guidesJava Final Keyword: Usage and Behavior
How Java's final keyword works for variables, methods, and classes, with practical examples and decision guidance for using it.
Java Final Variable: Syntax, Behavior, and Use Cases
Understand what a final variable in Java means, how initialization works, and when to use it for constants, immutability, and clearer code.
Java Duration vs Period: When to Use Each
java duration vs period: Compare Java Duration and Period to handle time-based and date-based calculations correctly. Learn syntax, conversion, and pitfalls.
Instance vs Static Variables in Java: Key Differences
Understand the difference between instance and static variables in Java, including memory, lifecycle, and when to use each.
More in Java
All Java guidesThe guides filed next to this one in Java, in library order.