Каким образом реализована хранение элементов внутри структуры ArrayList в Java?

В Java структура ArrayList реализована на основе динамического массива. Внутри ArrayList хранится обычный массив объектов (Object[] elementData), который увеличивается по мере необходимости.

Когда добавляется новый элемент и текущий массив заполнен, создаётся новый массив большего размера (обычно примерно в 1.5 раза больше), и все элементы копируются в него. Это позволяет эффективно обращаться к элементам по индексу (операция за O(1)), но вставка или удаление элементов в середине списка требует сдвига элементов.

Пример упрощённой внутренней реализации:

private transient Object[] elementData;
private int size;

public boolean add(E e) {
    ensureCapacity(size + 1);
    elementData[size++] = e;
    return true;
}

private void ensureCapacity(int minCapacity) {
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // увеличиваем на 50%
    if (newCapacity < minCapacity)
        newCapacity = minCapacity;
    elementData = Arrays.copyOf(elementData, newCapacity);
}