Java ArrayList

ArrayList<E> es la implementación de List más utilizada. Internamente es un array Java simple (Object[]) con un contador de longitud y algo de lógica de crecimiento encima. Esto le da la forma de rendimiento que la mayoría del código necesita: acceso aleatorio O(1), agregado amortizado O(1) al final, y solo una pausa ocasional cuando el array de respaldo tiene que crecer. Cuando alguien dice "usa una lista" sin especificar cuál, casi siempre se refiere a ArrayList. Este capítulo explica por qué, cuáles son las compensaciones y el puñado de métodos únicos de la clase.

Qué hay dentro

Un ArrayList mantiene tres piezas de estado:

• Object[] elementData — el array de respaldo. Es más grande que size con algo de margen.
• int size — cuántas de esas ranuras están en uso.
• int modCount — un contador que hace fallar a los iteradores si muta mientras se itera.

El Javadoc es preciso sobre la complejidad: size, isEmpty, get, set, iterator, listIterator y add (al final) se ejecutan en tiempo constante. Insertar o eliminar en cualquier otro lugar es lineal porque la cola del array tiene que desplazarse. Volvemos a eso más adelante.

Creando uno

List<String> a = new ArrayList<>();             // default capacity (10)
List<String> b = new ArrayList<>(1_000_000);    // pre-size — avoids re-grows
List<String> c = new ArrayList<>(otherList);    // copy of any Collection
List<String> d = new ArrayList<>(List.of("a", "b", "c"));   // from a small literal

Si sabes aproximadamente cuántos elementos vas a agregar, pasa la capacidad al constructor. La capacidad predeterminada es 10, y cada vez que el array se llena crece aproximadamente un 50 % — lo que significa muchas asignaciones y copias si agregas millones de elementos empezando desde el valor predeterminado. Solución de una línea:

List<Row> rows = new ArrayList<>(expectedSize);

Para "desde este conjunto fijo", prefiere la fábrica List.of(...) (cubierta más adelante en este capítulo) — es más pequeña e inmutable.

Agregar y eliminar — el costo depende de dónde

Cada List.add(E) y add(int, E) y remove(int) y remove(Object) es O(n) en el peor caso si toca el medio del array. El motivo es mecánico: un array es memoria contigua, por lo que insertar al frente significa que cada elemento existente tiene que moverse una ranura a la derecha. El costo amortizado de agregar al final es O(1) (sin desplazamiento), pero cualquier otra posición es lineal en el número de elementos después del punto de inserción.

En la práctica eso significa:

• Construir una lista mediante list.add(x) repetido → rápido, independientemente del tamaño. Agregar al final es para lo que sirve ArrayList.
• Llamar a list.add(0, x) en un bucle → cuadrático. No lo hagas.
• Llamar a list.remove(0) repetidamente para vaciar → cuadrático. Usa una Deque o itera en reversa.

Si te encuentras insertando o eliminando constantemente al frente, ArrayDeque es la herramienta adecuada.

Capacidad vs. tamaño

Estos son dos números diferentes:

• size() es el recuento de elementos a nivel público y de contrato.
• La capacidad — la longitud del array de respaldo — es interna y mayor que size.

Cuando se agota el margen, ArrayList asigna un nuevo array aproximadamente 1,5× la longitud anterior y copia. Eso es el "crecimiento" sobre el que advierte el Javadoc. Dos palancas de control:

• ensureCapacity(int) — incrementa el array de respaldo a al menos esa longitud antes de una ráfaga conocida de llamadas add.
• trimToSize() — reduce el array de respaldo exactamente a size. Útil cuando ya sabes que la lista no crecerá más (por ejemplo, antes de almacenarla en caché por mucho tiempo).

Ninguna es algo que uses frecuentemente, pero vale la pena saber que existen cuando estás optimizando un camino crítico.

ArrayList no es seguro para subprocesos

Dos subprocesos modificando el mismo ArrayList eventualmente lo corromperán. No hay sincronización, ni operación atómica, nada. Si necesitas acceso concurrente, tus opciones son:

• Collections.synchronizedList(new ArrayList<>()) — envuelve cada mutador en un bloqueo. Los iteradores aún no son seguros — tienes que sincronizar externamente durante la iteración. Está bien para casos de poca contención.
• CopyOnWriteArrayList — cada mutación asigna una nueva copia del array de respaldo. La iteración no requiere bloqueo y ve una instantánea congelada. Ideal para "muchos lectores, escritor ocasional" (oyentes de eventos, cachés de configuración). Terrible para cargas de trabajo de escritura intensiva.
• Vector — también sincronizado, pero un diseño de 1995 con las mismas debilidades que synchronizedList. No lo elijas para código nuevo.

El manejo de subprocesos es un tema profundo en sí mismo; por ahora, la regla es: un ArrayList compartido entre subprocesos necesita un envoltorio o una clase diferente.

Iteración y ConcurrentModificationException

Agregar o eliminar de un ArrayList mientras se itera sobre él mediante el bucle for-each casi siempre lanza ConcurrentModificationException:

List<Integer> xs = new ArrayList<>(List.of(1, 2, 3, 4));
for (int x : xs) {
  if (x % 2 == 0) xs.remove(Integer.valueOf(x));   // throws
}

La comprobación fail-fast compara la instantánea del modCount del iterador con el modCount actual de la lista. Las dos formas de mutar de forma segura:

xs.removeIf(x -> x % 2 == 0);              // 1. predicate form — cleanest

Iterator<Integer> it = xs.iterator();
while (it.hasNext())                        // 2. explicit Iterator.remove()
  if (it.next() % 2 == 0) it.remove();

removeIf es el valor predeterminado moderno. Recurre al iterador explícito solo cuando la condición depende de un estado que no quieres calcular dos veces.

Métodos útiles que no viste en List

ArrayList agrega algunos métodos que la interfaz List no tiene:

• void trimToSize() — reduce para ajustarse.
• void ensureCapacity(int) — pre-crecimiento.
• Object clone() — copia superficial. Equivalente a new ArrayList<>(this) y casi nunca se usa.

Eso es todo. Casi todo lo que llames en un ArrayList proviene de la interfaz List.

Un ejemplo práctico: ArrayList en acción

El programa a continuación construye un ArrayList, ejercita sus operaciones basadas en índices, lo vacía y termina con la diferencia de tiempo entre pre-crecimiento de capacidad vs. crecimiento predeterminado para que puedas ver el costo de olvidar el pre-dimensionado.

El orden de operaciones a leer en la salida:

• fruits.add(1, "avocado") desplazó cada elemento posterior una ranura a la derecha. Para cuatro elementos eso es invisible; para un millón dominaría el tiempo de ejecución.
• removeIf y subList son las dos piezas de maquinaria que hacen que la mayoría del código real de ArrayList sea limpio — eliminación masiva basada en predicados y operaciones de ventana en vivo.
• El bloque de tiempo es ilustrativo, no de nivel de referencia — en una sola ejecución de calentamiento JIT los números pueden incluso salir al revés. El punto que hace es estructural: el agregado de capacidad predeterminada vuelve a crecer el array de respaldo unas 30 veces para el millonésimo elemento, y el pre-dimensionado elimina cada una de esas copias. Para un camino crítico en estado estable la versión pre-dimensionada gana; mide con un arnés adecuado si importa.

Qué sigue

ArrayList es la respuesta correcta casi siempre. El caso interesante es cuando no lo es — inserción y eliminación intensiva al frente o en el medio de una lista larga. Ese es el nicho de LinkedList: la misma interfaz List, almacenamiento completamente diferente. Mismo problema, dos respuestas — y mediremos cuándo gana cada uno.

Práctica