Deque Implementations in Java – Which One to Use?
June 7, 2022In 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.
| Class | Thread- safe? | Blocking/ non-blocking | Fairness policy | Bounded/ unbounded | Iterator Type |
|---|---|---|---|---|---|
| ArrayDeque | No | Non-blocking | — | Unbounded | Fail-fast¹ |
| LinkedList | No | Non-blocking | — | Unbounded | Fail-fast¹ |
| ConcurrentLinkedDeque | Yes (optimistic locking via compare-and-set) | Non-blocking | — | Unbounded | Weakly consistent² |
| LinkedBlockingDeque | Yes (pessimistic locking with a lock) | Blocking | Not available | Bounded | Weakly 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:
ArrayDequefor single-threaded applicationsConcurrentLinkedDequeas a thread-safe, non-blocking, and unbounded dequeLinkedBlockingDequeas a thread-safe, blocking, bounded deque
Here is my recommendation as a decision tree:
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.