Как реализован ArrayList внутри?

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

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

Ключевые поля класса ArrayList:

• Object[] elementData — массив, в котором фактически хранятся данные.
• int size — текущее количество элементов в списке (не путать с длиной массива).

При создании ArrayList можно задать начальную ёмкость (initial capacity). Если не задать, используется значение по умолчанию (например, 10 в OpenJDK). Ёмкость — это длина внутреннего массива, а size — сколько ячеек уже занято.

Динамическое расширение

Когда вы добавляете новый элемент (метод add) и массив уже заполнен (size == elementData.length), происходит автоматическое увеличение ёмкости. Стандартная логика: создаётся новый массив большего размера (обычно старый_размер * 1.5), все элементы копируются в него, и ссылка elementData начинает указывать на новый массив. Этот процесс называется resizing (изменение размера) и требует времени O(n).

Пример кода

// Упрощённая иллюстрация метода add
public boolean add(E e) {
    ensureCapacityInternal(size + 1); // Проверяем, нужно ли увеличивать массив
    elementData[size++] = e; // Добавляем элемент в конец
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity); // Вызываем расширение
    }
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // Увеличиваем в ~1.5 раза
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    elementData = Arrays.copyOf(elementData, newCapacity); // Копируем в новый массив
}

Производительность и применение

Благодаря массиву внутри, ArrayList обеспечивает:

• Быстрый доступ по индексу (get/set) за O(1).
• Добавление в конец в среднем за O(1), но при необходимости расширения — O(n).
• Вставка или удаление из середины/начала требует сдвига всех последующих элементов, что выполняется за O(n).

ArrayList идеально подходит для сценариев, где преобладает чтение и последовательное добавление в конец, а частые вставки в середину или начало редки. Если же такие операции часты, лучше рассмотреть LinkedList.

Итог: Понимание внутреннего массива и механизма расширения помогает писать эффективный код, например, задавать начальную ёмкость, если известно примерное количество элементов, чтобы избежать многократных дорогостоящих операций копирования при добавлении.