Java – Do any Java libraries provide a random access Queue implementation


I'm implementing a sliding window over a stream of events, in Java.
So I want a data structure which allows me to do the following:

  1. add to the end of the data structure when new events occur;

  2. remove from the start of the data structure when old events are processed;

  3. get standard random access (size(), get(i)) to the elements of the data structure; in general, typical List "read" operations;

  4. is efficient for all of the above operations;

  5. is unbounded.

No other access is required. And no thread safety is required.

I'm currently doing this with an ArrayList, to get things up and running. But I want something more efficient; the remove(0) method (2. above) is inefficient with an ArrayList.

Numbers 1. and 2. are standard Queue-style operations. However, the implementations of Queue in the JDK (such as ArrayDeque) don't allow for get(i) in 3.

So, I'm wondering if there are any libraries out there which have such an implementation, and are suitable for commercial use.

If not, I guess I'll resort to writing my own…

Best Solution

Seems like a task for a Circular Buffer - as long as it's okay if the queue has a fixed capacity. I don't know of any standard implementation though. But here is a nice recipe to roll your own.

Related Question