La clase ArrayList en Java es una de las colecciones más utilizadas del paquete java.util.
Está implementada internamente sobre un arreglo dinámico, y su código fuente se encuentra en java.util.ArrayList dentro del JDK.
Veamos cómo funciona en detalle:
Internamente, ArrayList mantiene un array (arreglo) de tipo Object[] llamado elementData donde guarda los elementos:
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;
private int size;
}
- elementData: el arreglo donde se almacenan los elementos.
- size: la cantidad actual de elementos.
- DEFAULT_CAPACITY: capacidad inicial (10).
- EMPTY_ELEMENTDATA: usado cuando el ArrayList está vacío.
Cuando creás un ArrayList sin indicar capacidad:
List<String> list = new ArrayList<>();
internamente no se reserva espacio aún. Se crea con elementData = EMPTY_ELEMENTDATA.
Recién al agregar el primer elemento, se inicializa con una capacidad por defecto (10).
Cuando llamás a:
list.add("Hola");
Java hace esto internamente:
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
Y ensureCapacityInternal verifica si el arreglo tiene espacio suficiente:
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
Si no hay espacio, llama a grow():
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 veces más
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}
Cuando se queda sin espacio, duplica la capacidad en un 50% (crecimiento amortizado).
Acceder es O(1) porque es un arreglo:
public E get(int index) {
rangeCheck(index);
return (E) elementData[index];
}
Cuando quitás un elemento:
list.remove(2);
se mueve el resto de los elementos para no dejar “huecos”:
public E remove(int index) {
rangeCheck(index);
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
elementData[--size] = null; // libera la referencia
return oldValue;
}
Esto hace que remove sea O(n) en el peor caso (por el corrimiento de elementos).
Veamos ventajas y desventajas
Ventajas:
- Acceso aleatorio rápido (O(1)).
- Memoria contigua, lo que mejora la localidad de referencia.
- Crece automáticamente.
Desventajas:
- Insertar o eliminar en el medio es costoso (O(n)).
- Aumentar la capacidad implica copiar el arreglo completo.
ArrayList es básicamente una versión moderna y no sincronizada de Vector.
Si necesitás sincronización, podés envolverlo así:
List<String> syncList = Collections.synchronizedList(new ArrayList<>());