linkedlist - Equivalente en Java de std:: deque

queue java library

Question

Soy un programador de Java relativamente nuevo que proviene de C ++ / STL, y estoy buscando una clase con estas características (que C ++ std :: deque tiene, según tengo entendido):

1. O (1) rendimiento para la inserción / eliminación al principio / final
2. O (1) rendimiento para la búsqueda por índice
3. son colecciones cultivables (no necesitan límites de tamaño fijo)

¿Hay un Java equivalente a esto? Encontré la clase Java 1.6 [ArrayDeque] que tiene las características de inserción / eliminación y de crecimiento, pero no parece tener búsqueda por índice a menos que llame a Array () que no sería O (1).

Answer 1

Mi enfoque predeterminado sería hackear mi propia clase, con ArrayList como una implementación subyacente (por ejemplo, asignar los índices de mi propia clase a los índices ArrayList) ... pero odio reinventar la rueda, especialmente cuando hay una buena posibilidad de joder ...

Answer 2

Primitive Collections para Java tiene un ArrayDeque con un método get (int idx).

http://sourceforge.net/projects/pcj

Sin embargo, no puedo garantizar la calidad de este proyecto.

Una alternativa sería obtener la fuente JDK ArrayDeque y agregar el método get (int idx) usted mismo. Debería ser relativamente fácil.

EDITAR: Si tiene la intención de utilizar el deque de una manera muy multihilo, iría a la ruta "parchear el ArrayDeque del JDK". Esta implementación se ha probado exhaustivamente y se usa en el nuevo marco de ForkJoin de java.util.concurrent.

Answer 3

Es interesante ... Estaba terminando de leer Genéricos y Colecciones de Java y tiene una breve discusión de este tipo de colección, que incluye un enlace al Boletín de Especialistas de Java, que incluye una CircularArrayList que podría hacer lo que necesito.

Answer 4

Aquí hay un buffer circular listo para usar implementado en Java, CircularArrayList . Sin embargo, no es cultivable después de la creación. ( Descargo de responsabilidad: Este enlace apunta a mi propio sitio web )

La otra opción que flota en la web sería la del boletín informativo de especialistas de Java . Nunca usé ese, por las siguientes razones:

1. Está incompleto - ("Este método se dejó como un ejercicio para el lector")
2. No es compatible con el tipo de elemento genérico, ya que habría sido coherente con otras colecciones del Marco de la Colección de Java.
3. Es innecesariamente complicado y, por lo tanto, posiblemente con errores, en lugar de seguir el procedimiento de extensión recomendado por el Javadoc de AbstractList.