Как работает механизм расширения массива в ArrayList?

ArrayList в Java — это реализация интерфейса List на основе динамически изменяемого массива. Ключевое преимущество перед обычным массивом — возможность автоматического изменения размера при добавлении элементов, что избавляет разработчика от ручного управления памятью.

Внутреннее устройство

Внутри ArrayList хранит элементы в обычном массиве (поле elementData). При создании ArrayList можно указать начальную ёмкость (capacity) — размер этого внутреннего массива. Если ёмкость не указана, используется значение по умолчанию, которое в современных версиях JDK равно 10.

Процесс расширения (Grow)

Когда вызывается метод add(E e) и внутренний массив уже заполнен (т.е. size == elementData.length), запускается механизм расширения:

1. Вычисляется новая ёмкость. Стандартная формула: newCapacity = oldCapacity + (oldCapacity >> 1). Сдвиг вправо на 1 бит эквивалентен делению на 2, поэтому увеличение составляет примерно 50% (например, с 10 до 15).
2. Создаётся новый массив объектов этого нового размера.
3. Все элементы из старого массива копируются в новый с помощью System.arraycopy() — это нативная быстрая операция.
4. Ссылка elementData начинает указывать на новый массив, а старый массив становится доступным для сборщика мусора.
5. Новый элемент добавляется в конец нового массива.

Пример кода, иллюстрирующий процесс

import java.util.ArrayList;

public class ArrayListGrowthDemo {
    public static void main(String[] args) {
        // Создаём ArrayList с начальной ёмкостью по умолчанию (10)
        ArrayList list = new ArrayList<>();
        
        // Добавляем 11 элементов, чтобы вызвать расширение
        for (int i = 0; i < 11; i++) {
            list.add(i);
            // На 11-м добавлении (i=10) произойдёт расширение
            // Внутренний массив увеличится с 10 до 15
        }
        
        System.out.println("Размер списка: " + list.size());
        // Можно проверить ёмкость через reflection (не рекомендуется в production)
    }
}

Амортизированная сложность и оптимизация

Операция расширения стоит O(n), так как требует копирования всех элементов. Однако, поскольку расширение происходит не при каждом добавлении, а лишь периодически, амортизированная стоимость одной операции add остаётся O(1). Это делает ArrayList эффективным для сценариев, где преобладает последовательное добавление в конец.

Если заранее известно примерное количество элементов, стоит использовать конструктор ArrayList(int initialCapacity) или метод ensureCapacity(), чтобы задать достаточную начальную ёмкость. Это позволяет избежать многократных дорогостоящих операций копирования при заполнении списка.

Вывод: Механизм расширения ArrayList — это компромисс между производительностью и удобством. Он идеально подходит для случаев, когда нужно часто получать доступ к элементам по индексу (O(1)) и добавлять данные в конец, но не подходит для частых вставок в начало или середину (где LinkedList может быть лучше). Понимание этого механизма помогает писать более эффективный код, минимизируя ненужные расширения.