Complejidad de tiempo para java ArrayList

¿ ArrayList es una matriz o una lista en Java? ¿Cuál es la complejidad de tiempo para la operación get, es O(n) u O(1) ?

Una ArrayList en Java es una List respaldada por una array .

El método get(index) es una operación de tiempo constante, O(1) .

El código directamente de la biblioteca Java para ArrayList.get(index) :

 public E get(int index) { RangeCheck(index); return (E) elementData[index]; } 

Básicamente, simplemente devuelve un valor directamente de la matriz de respaldo. ( RangeCheck(index) ) también es tiempo constante

Su implementación se realiza con una matriz y la operación get es O (1).

javadoc dice:

Las operaciones size, isEmpty, get, set, iterator y listIterator se ejecutan en tiempo constante. La operación de adición se ejecuta en tiempo constante amortizado , es decir, agregar n elementos requiere O (n) tiempo. Todas las demás operaciones se ejecutan en tiempo lineal (aproximadamente hablando). El factor constante es bajo comparado con el de la implementación LinkedList.

Como todos ya han señalado, las operaciones de lectura son de tiempo constante – O (1) pero las operaciones de escritura tienen el potencial de quedarse sin espacio en la matriz de respaldo, reasignación y una copia, por lo que se ejecuta en O (n) tiempo , como dice el documento:

Las operaciones size, isEmpty, get, set, iterator y listIterator se ejecutan en tiempo constante. La operación de adición se ejecuta en tiempo constante amortizado, es decir, agregar n elementos requiere O (n) tiempo. Todas las demás operaciones se ejecutan en tiempo lineal (aproximadamente hablando). El factor constante es bajo comparado con el de la implementación LinkedList.

En la práctica todo es O (1) después de algunas adiciones, ya que la matriz de respaldo se duplica cada vez que se agota su capacidad. Entonces, si la matriz comienza en 16, se llena, se reasigna a 32, luego a 64, 128, etc., por lo que escalan bien, pero GC puede golpear durante un realloc grande.

Para ser pedante, es una List respaldada por una matriz. Y sí, la complejidad de tiempo para get() es O (1).

Solo una nota.

El método get(index) es un tiempo constante, O(1)

Pero ese es el caso si conocemos el índice. Si tratamos de obtener el índice usando indexOf(something) , eso costará O(n)