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][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][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][queue]-style operations. However, the implementations of `Queue` in the JDK (such as [ArrayDeque][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... [list]:http://java.sun.com/javase/6/docs/api/java/util/List.html [arraylist]:http://java.sun.com/javase/6/docs/api/java/util/ArrayList.html [queue]:http://java.sun.com/javase/6/docs/api/java/util/Queue.html [arraydeque]:http://java.sun.com/javase/6/docs/api/java/util/ArrayDeque.html
How relatively-frequent are these operations? You may have to trade some serious space for time -- e.g. you could use a cicularly linked list with an index for rapid retrieval (index: I forget the name for this structure; a binary tree of pointers to 0 and n/2, each of which stores pointers to the midpoint of their half, etc.).