Java Deque Implementations - Which one to use?Java Deque Implementations - Which one to use?
HappyCoders Glasses

Deque Implementations Which One to Use?

Sven Woltmann
Sven Woltmann
June 7, 2022

In the previous parts of this tutorial series, you have learned about all the Deque implementations of the JDK. In this article, I'll help you decide when you should use which implementation.

In the table, the deque names are linked to the article in which that deque and its specific characteristics are described.

For explanations of the terms blocking, non-blocking, fairness policy, bounded, and unbounded, see the article about the BlockingQueue interface.

ClassThread-
safe?
Blocking/
non-blocking
Fairness
policy
Bounded/
unbounded
Iterator Type
ArrayDequeNoNon-blockingUnboundedFail-fast¹
LinkedListNoNon-blockingUnboundedFail-fast¹
ConcurrentLinkedDequeYes
(optimistic locking via compare-and-set)
Non-blockingUnboundedWeakly consistent²
LinkedBlockingDequeYes
(pessimistic locking with a lock)
BlockingNot availableBoundedWeakly consistent²

¹ Fail-fast: The iterator throws a ConcurrentModificationException if elements are inserted into or removed from the deque during iteration.

² Weakly consistent: All elements that exist when the iterator is created are traversed by the iterator exactly once. Changes that occur after this can, but do not need to, be reflected by the iterator.

When to Use Which Deque Implementation?

Based on the characteristics explained in the previous parts of the series and summarized in the table above, you can choose the right deque for your specific application.

My recommendations are:

  • ArrayDeque for single-threaded applications
  • ConcurrentLinkedDeque as a thread-safe, non-blocking, and unbounded deque
  • LinkedBlockingDeque as a thread-safe, blocking, bounded deque

Here is my recommendation as a decision tree:

Decision tree Java deque implementations
Decision tree Java deque implementations

You probably notice that LinkedList is missing here. The reason is that I generally advise against using LinkedList as a deque.

Summary and Outlook

In this article, I've provided an overview of all the Deque implementations and a decision-making guide for when you should use which implementation.

In the next part, I'll show you how to implement a deque using an array.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.