Что под капотом у ArrayList

Под капотом у ArrayList: структура и механизмы

ArrayList в Java (и его аналог в Android/Kotlin) — это реализация динамически расширяемого массива, которая предоставляет удобный интерфейс для работы с упорядоченными коллекциями. Его ключевая особенность — сочетание быстрого произвольного доступа (как у массива) с автоматическим управлением ёмкостью. Разберём, как это работает на низком уровне.

1. Внутреннее хранилище: обычный массив

В основе ArrayList лежит простой массив (Object[] для Java, Array<T> для Kotlin). Именно в нём и хранятся все добавленные элементы.

// Упрощённый взгляд на внутренности ArrayList (Java)
public class ArrayList<E> {
    // Внутренний массив для хранения данных
    transient Object[] elementData;
    
    // Количество реально хранящихся элементов
    private int size;
}

Размер (size) — это количество элементов, которые фактически добавлены в список. Ёмкость (capacity) — это длина внутреннего массива elementData, которая всегда >= size. Различие между size и capacity — ключ к пониманию работы ArrayList.

2. Динамическое расширение: как растёт массив

Изначально при создании ArrayList() внутренний массив инициализируется с емкостью по умолчанию (например, 10 в Java 7+, 0 в некоторых версиях Kotlin для оптимизации памяти). Когда мы добавляем элементы с помощью add(element), происходит следующее:

1. Проверяется, есть ли свободное место: size < elementData.length.
2. Если место есть — элемент помещается в массив по индексу size, и size увеличивается на 1.
3. Если места нет — запускается процесс расширения (resize):
   • Создаётся новый массив большего размера (обычно в 1.5 раза в Java, oldCapacity + (oldCapacity >> 1)).
   • Все элементы из старого массива копируются в новый с помощью System.arraycopy().
   • Ссылка elementData начинает указывать на новый массив.
   • Добавляемый элемент помещается в конец.

// Примерная логика расширения
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);
}

Этот процесс делает добавление амортизированно быстрым — хотя отдельные операции расширения дороги (O(n)), в среднем добавление остаётся O(1).

3. Ключевые операции и их сложность

• Получение элемента по индексу get(index): O(1) — прямое обращение к массиву.
• Добавление в конец add(element): O(1) в среднем, O(n) при расширении.
• Добавление в середину add(index, element): O(n) — требует сдвига части массива.
• Удаление элемента remove(index): O(n) — аналогично требует сдвига.
• Поиск по значению indexOf(element): O(n) — линейный перебор.

4. Особенности в Android/Kotlin

В Kotlin ArrayList — это typealias на java.util.ArrayList, но есть оптимизации:

• ArrayList() в Kotlin создаёт список с нулевой ёмкостью для экономии памяти, расширяясь только при первом добавлении.
• Используются generic-массивы (Array<Any?>), что обеспечивает безопасность типов.
• Добавлены функции-расширения для удобной работы: toMutableList(), filter, map и т.д.

// Kotlin: создание и использование
val list = ArrayList<String>()
list.add("Android") // При первом добавлении происходит первое расширение
println(list[0]) // Быстрый доступ по индексу

5. Важные аспекты реализации

• Не синхронизирован — небезопасен для использования из нескольких потоков без внешней синхронизации.
• Позволяет дубликаты и null (если тип поддерживает null).
• Итератор fail-fast — при изменении списка во время итерации выбрасывается ConcurrentModificationException.
• Обрезка ёмкости с помощью trimToSize() освобождает неиспользуемую память.
• Клонирование создаёт поверхностную копию — элементы не копируются.

Заключение

ArrayList — это компромисс между производительностью и удобством. Его сила — быстрый произвольный доступ и эффективное добавление в конец благодаря стратегии умного расширения массива. Слабость — дорогое вставление/удаление в середину. Понимание этих механизмов позволяет выбирать ArrayList для сценариев с частым доступом по индексу и редкими структурными изменениями, а также правильно оценивать производительность при работе с большими объёмами данных. В Android-разработке это одна из самых часто используемых структур данных благодаря балансу скорости и гибкости.