Translate

jueves, 9 de octubre de 2025

Hablemos de ArrayList


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<>());