¿Cuál es la complejidad de agregar un elemento a ArrayList?

La complejidad de agregar un elemento a ArrayList en el caso promedio es O(1).

Esto se logra mediante el uso de un array dinámico, y la adición ocurre al final de la lista.

// Agregar al final de la lista
List<String> list = new ArrayList<>();
list.add("elemento"); // O(1) en promedio

Sin embargo, en el caso de que el array interno de ArrayList esté lleno, se requiere una operación de aumento de tamaño (resize). Esto implica crear un nuevo array más grande y copiar todos los elementos existentes en el nuevo array. La complejidad de esta operación es O(n), donde n es el tamaño actual de la lista.

// Ejemplo donde puede ocurrir resize
List<Integer> numbers = new ArrayList<>(3); // Capacidad inicial de 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Aquí puede ocurrir resize - O(n)

Si el elemento se agrega no al final de la lista (método add(int index, E element)), sino en medio o al principio, se requiere desplazar todos los elementos posteriores una posición hacia la derecha. La complejidad de esta operación es O(n), donde n es la cantidad de elementos que deben desplazarse.

// Agregar al principio de la lista
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Agregar al principio - O(n)

Por lo tanto, la complejidad de agregar un elemento a ArrayList depende del lugar donde se agregue y de la necesidad de resize:

Operación de agregar	Caso promedio	Peor caso (durante resize o no agregar al final)
add(E element) (al final)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)