Как ArrayList увеличивает свою внутреннюю емкость (capacity)?

ArrayList в Java использует внутренний массив (Object[] elementData). При добавлении элемента, если массив заполнен, происходит операция расширения (resize).

Алгоритм расширения (в OpenJDK):

1. Проверяется, достигнут ли текущий размер (size) емкости массива (capacity).
2. Если да, вызывается приватный метод grow().
3. Новая емкость вычисляется по формуле: newCapacity = oldCapacity + (oldCapacity >> 1).
   • oldCapacity >> 1 — это побитовый сдвиг вправо, эквивалентный целочисленному делению oldCapacity на 2.
   • Итог: новая емкость примерно в 1.5 раза больше старой (если oldCapacity > 0).
4. Создается новый массив вычисленного размера.
5. Все элементы из старого массива копируются в новый с помощью Arrays.copyOf (или System.arraycopy).
6. Ссылка elementData начинает указывать на новый массив. Старый массив становится недостижимым и впоследствии удаляется сборщиком мусора (GC).

Пример пошагово:

// Начальное состояние: ArrayList с конструктором по умолчанию (capacity=10)
ArrayList<Integer> list = new ArrayList<>();

// Добавляем 10 элементов
for (int i = 0; i < 10; i++) { list.add(i); } // elementData.length = 10, size = 10

// Добавление 11-го элемента вызывает расширение
list.add(10);
// 1. oldCapacity = 10
// 2. newCapacity = 10 + (10 >> 1) = 10 + 5 = 15
// 3. Создается новый массив на 15 элементов, копируются старые 10.
// 4. В 11-ю ячейку (index 10) записывается значение 10.
// Итог: elementData.length = 15, size = 11.

Важные следствия и best practices:

• Сложность операции: Расширение и копирование — операция O(n), где n — старый размер. Это дорого.
• Инициализация с известной capacity: Если примерное количество элементов известно, всегда задавайте начальную емкость в конструкторе: new ArrayList<>(1000). Это предотвращает многократные дорогостоящие расширения.
• Минимальное расширение: При добавлении одного элемента в пустой список (capacity=0) первое расширение создает массив емкостью DEFAULT_CAPACITY = 10. Последующие расширения идут по правилу x1.5.