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

O (1) rendimiento para inserción / extracción al principio / finalO (1) rendimiento para búsqueda por índiceson colecciones ampliables (no necesitan límites de tamaño fijos)

¿Hay un equivalente de Java para 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 toArray () que no sería O (1).