Java equivalent of std::deque

Question

I'm a relatively new Java programmer coming from C++/STL, and am looking for a class with these characteristics (which the C++ std::deque has, as I understand it):

1. O(1) performance for insertion/removal at the beginning/end
2. O(1) performance for lookup by index
3. are growable collections (don't need fixed size bounds)

Is there a Java equivalent to this? I found the Java 1.6 [ArrayDeque] class which has the insert/removal and growable characteristics, but don't seem to have lookup-by-index unless you call toArray() which would not be O(1).

Answer 1

Primitive Collections for Java has an ArrayDeque with a get(int idx) method.

http://sourceforge.net/projects/pcj

I can't vouch for the quality of this project though.

An alternative would be to get the JDK ArrayDeque source and add the get(int idx) method yourself. Should be relatively easy.

EDIT: If you intend to use the deque in a highly multi-threaded manner, I would go the "patch the JDK's ArrayDeque" route. This implementation has been tested thoroughly and is used in the new java.util.concurrent ForkJoin framework.

Answer 2

My default approach would be to hack together my own class, with ArrayList as an underlying implementation (e.g. map my own class's indices to ArrayList indices)... but I hate reinventing the wheel especially when there's a good chance of screwing up...

Answer 3

Interesting... I was just finishing reading Java Generics and Collections and it has a brief discussion of this kind of collection including a link to the Java Specialists' Newsletter which includes a CircularArrayList that might do what I need.

Answer 4

Here is a ready-to-use circular buffer implemented in Java, CircularArrayList. It isn't growable after creation, though. (Disclaimer: This link points to my own website)

The other option floating around the web would be the one from the Java Specialists Newsletter. I never used that one, for the following reasons:

1. It is incomplete - ("This method left as an exercise to the reader")
2. It does not support generic element type as would have been consistent with other collections from the Java Collection's Framework.
3. It is unnecessarily complicated, and therefore possibly buggy, instead of following the extension procedure recommended by AbstractList's Javadoc.