Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

Java Deque: Double-Ended Queue in Practice

Learn how to use Java's Deque interface for double-ended queues, stacks, and FIFO queues, including implementation choices and performance tradeoffs.

~7 min readJava
#Deque#ArrayDeque#LinkedList#Java Collections
Illustration of a double-ended queue data structure with elements entering and leaving from both ends.

The java.util.Deque interface models a double-ended queue: a collection that supports insertion and removal at both ends. It was introduced in Java 6 and is part of the Java Collections Framework. If you have ever used ArrayDeque or LinkedList in a Deque variable, you have already worked with it. What matters in practice is understanding which methods are available, how the two main implementations differ, and when a Deque is the right choice over a plain Queue or Stack.

The Deque Interface and Its Core Methods

The Deque interface extends Queue and adds methods that operate on both ends. The naming convention gives you two families of methods: one that throws an exception when the operation fails, and one that returns a special value (null or false).

OperationThrows exceptionReturns special value
Insert at headaddFirst(e)offerFirst(e)
Insert at tailaddLast(e)offerLast(e)
Remove at headremoveFirst()pollFirst()
Remove at tailremoveLast()pollLast()
Examine at headgetFirst()peekFirst()
Examine at tailgetLast()peekLast()

The exception-throwing variants are useful when you know the operation must succeed and you want a failure to be loud. The special-value variants are better when you are implementing a queue or stack where an empty state is a normal condition, not an error.

For example, a work queue that processes tasks should use pollFirst() to retrieve the next item, because an empty queue is an expected state. Using removeFirst() there would throw NoSuchElementException every time the queue drained.

java
Deque<Task> pending = new ArrayDeque<>(); // Producer pending.addLast(new Task("index-page")); // Consumer Task next = pending.pollFirst(); if (next != null) { process(next); }

Using a Deque as a Stack or a Queue

A Deque can replace both the legacy Stack class and the Queue interface. The Stack class in java.util is synchronized and carries a legacy design; the Deque interface is the recommended replacement in the Java documentation.

To use a Deque as a stack, you operate on only one end:

java
Deque<String> stack = new ArrayDeque<>(); stack.push("first"); stack.push("second"); String top = stack.pop(); // "second"

The push and pop methods are equivalent to addFirst and removeFirst. The peek method is equivalent to peekFirst(): it returns the head without removing it, or null when the stack is empty. This gives you LIFO behavior without the synchronization overhead of the legacy Stack class.

To use a Deque as a queue, you add at one end and remove at the other:

java
Deque<String> queue = new ArrayDeque<>(); queue.addLast("job-a"); queue.addLast("job-b"); String next = queue.removeFirst(); // "job-a"

This is FIFO behavior, and it is exactly what the Queue interface provides. The advantage of using a Deque is that you can switch between stack and queue behavior without changing the underlying collection type, and you can work with elements from both ends when needed.

ArrayDeque vs LinkedList

The two most common implementations of Deque are ArrayDeque and LinkedList. They have different memory and performance characteristics.

ArrayDeque is backed by a resizable array. It has no capacity restrictions, grows as needed, and is not synchronized. It does not support null elements. Because it uses an array, element access by index is not possible through the Deque interface, but the implementation itself is compact and cache-friendly.

LinkedList is a doubly-linked list. It also implements List, so you can use it as both a Deque and a List. It permits null elements. Each element is wrapped in a node object, which adds memory overhead per element and tends to scatter nodes across memory, reducing cache locality.

CharacteristicArrayDequeLinkedList
Backing structureResizable arrayDoubly-linked list
Null elementsNot allowedAllowed
Implements ListNoYes
Memory per elementCompactNode overhead
Cache localityGoodPoorer
Removal at endsO(1)O(1)

For most deque use cases, ArrayDeque is the better default. It uses less memory per element, has better cache behavior, and avoids the per-node allocation that LinkedList incurs. Choose LinkedList when you specifically need List functionality alongside deque behavior, or when you need to support null elements.

Performance Characteristics and Runtime Cost

Both ArrayDeque and LinkedList provide O(1) amortized time for adding and removing at the ends. The difference is in constant factors and memory behavior.

ArrayDeque grows by reallocating and copying when its internal array is full. This is amortized O(1), meaning the occasional resize is spread across many operations. The resizing strategy is implementation-dependent, so you should not rely on a specific growth factor. If you know the maximum number of elements in advance, you can pass an initial capacity to the constructor to avoid resizing:

java
Deque<Event> events = new ArrayDeque<>(10_000);

LinkedList allocates a new node for every insertion and deallocates it on removal. This causes more frequent garbage collection pressure than ArrayDeque, especially in high-throughput scenarios. For long-lived queues with many insertions and removals, ArrayDeque is usually the better choice.

One important limitation: ArrayDeque does not allow null elements. If your application relies on null as a sentinel value, you need either LinkedList or a different sentinel, such as Optional.empty().

Common Pitfalls with Deque Methods

A frequent mistake is mixing the exception-throwing and special-value method families without considering the semantics. For example, using getFirst() on an empty deque throws an exception, while peekFirst() returns null. When you drain a deque in a loop, prefer pollFirst() and check for null, or check isEmpty() before a removeFirst() call.

Another pitfall is using addFirst and addLast interchangeably without realizing the effect on iteration order. The iterator() of a Deque returns elements from head to tail. If you add elements with addFirst, the iteration order is reverse of insertion order. This is correct behavior, but it can surprise developers who expect insertion order.

A third issue is treating Deque as a thread-safe collection. None of the standard implementations are synchronized. If multiple threads access the same deque, you must synchronize externally or use a concurrent collection such as ConcurrentLinkedDeque. The Deque interface itself provides no thread-safety guarantee.

Choosing the Right Implementation for Your Use Case

The decision between ArrayDeque and LinkedList should be based on your actual requirements:

  • Use ArrayDeque when you need a stack or queue with good performance and you do not need List functionality.
  • Use LinkedList when you need to treat the collection as both a Deque and a List, or when null elements are required.
  • Use ConcurrentLinkedDeque when multiple threads will access the deque concurrently and you want lock-free behavior.
  • Use ArrayBlockingQueue or LinkedBlockingQueue when you need a blocking queue with capacity limits, not a general-purpose deque.

If you are writing a method that only needs to add at one end and remove at the other, consider accepting the Queue interface rather than Deque. This narrows the API surface and prevents callers from accidentally using deque-specific methods. Similarly, if you only need stack behavior, you can accept a Deque but document that only push, pop, and peek are used.

Deque and Null Elements: A Practical Constraint

ArrayDeque rejects null on insertion and throws NullPointerException. This is a deliberate design choice: the special-value methods (offerFirst, pollFirst, peekFirst) already use null to signal an empty deque, so allowing null elements would make it impossible to distinguish an empty deque from a deque containing a null element.

LinkedList allows null elements, which means you can store null in it. However, this creates the same ambiguity problem: pollFirst() returns null both when the deque is empty and when the first element is null. If you rely on null as a sentinel, you cannot distinguish these two cases. Prefer using Optional or a dedicated sentinel object instead.

Iteration and Bulk Operations

The Deque interface inherits Iterable and provides an iterator that traverses from head to tail. You can also obtain a reverse-order iterator with descendingIterator(). This is useful when you need to process a deque from the tail end without removing elements.

java
Deque<String> deque = new ArrayDeque<>(); deque.addLast("a"); deque.addLast("b"); deque.addLast("c"); Iterator<String> reverse = deque.descendingIterator(); while (reverse.hasNext()) { System.out.println(reverse.next()); // c, b, a }

Bulk operations such as addAll and removeAll are inherited from Collection. They operate on the deque as a whole, but they do not guarantee atomicity. If you need to add or remove multiple elements atomically, you must synchronize externally.

When a Deque Is Not the Right Tool

A Deque is not a general-purpose list. It does not support indexed access. If you need to retrieve the element at position 5, a Deque is the wrong choice; use an ArrayList or LinkedList as a List. Similarly, if you need to sort elements, copy them into a List first.

A Deque is also not a priority queue. If you need elements ordered by priority rather than insertion position, use PriorityQueue. The Deque interface only guarantees order based on where elements are inserted, not based on any comparator.

For concurrent scenarios, the ConcurrentLinkedDeque class provides thread-safe operations, but it does not block. If you need a blocking deque with capacity limits, LinkedBlockingDeque is the appropriate choice. The standard ArrayDeque and LinkedList are not safe for concurrent modification without external synchronization.

Final Implementation Guidance

When you declare a variable, use the Deque interface type rather than a concrete implementation. This lets you swap ArrayDeque for LinkedList without changing the rest of your code, and it signals to readers that only deque operations are intended. Reserve the concrete type for the constructor call.

java
Deque<Message> outbox = new ArrayDeque<>();

If you later discover that you need List behavior, you can change the declaration to LinkedList and keep the deque operations intact. The interface-based approach also makes unit testing simpler, because you can substitute a mock or a different implementation in tests.

For production code, prefer ArrayDeque as the default implementation. Its compact memory footprint and cache-friendly access pattern make it suitable for most stack and queue workloads. Reserve LinkedList for the specific cases where its List functionality or null support is genuinely required.

Try matching browser tools

All tools

Small utilities that fit Java work — they run entirely in this browser tab, so nothing you paste leaves your device.

All Java guides

More in Java

All Java guides

The guides filed next to this one in Java, in library order.