С помощью какой структуры данных реализован ArrayList

ArrayList в Java реализован на основе динамического массива. При создании выделяется начальный capacity (по умолчанию 10), который автоматически увеличивается при заполнении (обычно в 1.5 раза).

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

• Быстрый доступ по индексу (O(1))
• Медленные вставка/удаление в середине (O(n))
• Память выделяется непрерывным блоком

Пример увеличения capacity:

// Внутри ArrayList
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // Увеличение в ~1.5 раза
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Использует Object[] для хранения данных, что позволяет работать с любыми типами (с оверхедами из-за autoboxing для примитивов).