performance - What is the fastest Java collection with the basic functionality of a Queue?

Question

What is the fastest collection in Java?

I only need the operations to add and remove, order is not important, equals elements is not a issue, nothing more than add and remove is imporant.

Without limit size is important too.

These collection will have Objects inside him.

Currently I'm using ArrayDeque because I see this is the faster Queue implementation.

Answer 1

ArrayDeque is best. See this benchmark, which comes from this blog post about the results of benchmarking this. ArrayDeque doesn't have the overhead of node allocations that LinkedList does nor the overhead of shifting the array contents left on remove that ArrayList has. In the benchmark, it performs about 3x as well as LinkedList for large queues and even slightly better than ArrayList for empty queues. For best performance, you'll probably want to give it an initial capacity large enough to hold the number of elements it's likely to hold at a time to avoid many resizes.

Between ArrayList and LinkedList, it seems that it depends on the average number of total elements the queue will contain at any given time and that LinkedList beats ArrayList starting at about 10 elements.