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

В Java ArrayList реализован на основе массива. Когда текущий массив заполняется, и требуется добавить новый элемент, происходит увеличение внутреннего массива.

Механизм увеличения:

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

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

Примерно так выглядит увеличение:

int newCapacity = oldCapacity + (oldCapacity >> 1); // увеличение на 50%