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

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

Таким образом, элементы хранятся в непрерывном блоке памяти, что обеспечивает быстрый доступ по индексу (операция get(index) выполняется за константное время).

Пример упрощённой внутренней структуры:

private Object[] elementData;
private int size;

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

private void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length) {
        int newCapacity = elementData.length + (elementData.length >> 1);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

Таким образом, ArrayList обеспечивает динамическое расширение массива и быстрый доступ к элементам по индексу.

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