Что лежит в основе ArrayList?

Основа ArrayList

ArrayList в Java построен на основе динамического массива. В его основе лежит обычный массив Object[], который автоматически увеличивает свой размер при необходимости.

Внутренняя структура

public class ArrayList<E> extends AbstractList<E> {
    private static final int DEFAULT_CAPACITY = 10;
    transient Object[] elementData;
    private int size;
}

Ключевые компоненты:

1. elementData — массив для хранения элементов
2. size — текущее количество элементов
3. capacity — текущая емкость массива

Как это работает

Когда ArrayList создается, по умолчанию он инициализируется с capacity=10. При добавлении элемента (add()):

• Если size < capacity — элемент добавляется в свободное место
• Если size == capacity — создается новый массив большего размера (обычно 1.5x текущего размера) и все элементы копируются туда

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5x увеличение
    elementData = Arrays.copyOf(elementData, newCapacity);
}

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

• get(index) — O(1), прямой доступ по индексу
• add(element) — O(1) амортизированное (иногда O(n) при переаллокации)
• remove(index) — O(n), требует сдвига элементов
• add(index, element) — O(n), сдвиг элементов

Особенности

• Не синхронизирован (используй Collections.synchronizedList для многопоточности)
• Содержит нулевые элементы (null-safe)
• Быстр для доступа по индексу, медленнее для вставки/удаления
• Должен содержать только Object и его наследников

Наличие динамического массива в основе делает ArrayList универсальным решением для большинства случаев, требующих flexible collection.