A fast queue in Java

Question

I am looking for a fast queue implementation in Java. I see that LinkedList implements the Queue interface, but it will only be as fast as a LinkedList right? Is there a way to have a queue that will be faster especially for add (I only need poll, add and check for empty). Down the line I may also need a PriorityQueue but not yet.

Answer 1

If multiple threads are going to be accessing the queue then consider using an ArrayBlockingQueue. Otherwise take a look at ArrayDeque. From the ArrayDeque API:

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

Specifically an array-based queue implementation reduces the need to resize the underlying array if the existing array has sufficient capacity, thus making additions to the queue generally faster than LinkedList. Be aware that ArrayBlockingQueue is a bounded implementation whereas ArrayDeque will resize as required.

The flip-side is that LinkedList will typically provide a much more compact representation, particularly in cases where your queue grows and shrinks by a large amount. For example, if you added 10,000,000 elements to an ArrayDeque and then removed 9,999,999 elements, the underlying array would still be of length 10,000,000 whereas a LinkedList would not suffer from this problem.

In reality, for single-threaded access to a non-blocking queue I tend to favour LinkedList. I imagine the performance differences are so negligable you wouldn't notice the difference anyway.