sottoЧто внутри
ArrayList — это обёртка над обычным массивом Object[] elementData плюс поле size (число занятых элементов). Важно различать size (сколько элементов) и capacity (длина внутреннего массива): capacity ≥ size.
Доступ get(i)/set(i) — это просто индексирование массива, поэтому O(1) и с отличной cache locality: элементы лежат подряд в памяти, что дружит с процессорным кэшем и префетчем.
Рост массива
Когда при add массива не хватает, вызывается grow(): новая ёмкость = старая + (старая >> 1), то есть рост примерно в 1.5×, после чего старые элементы копируются в новый массив через System.arraycopy.
Коэффициент 1.5 — компромисс: больше (например 2×) реже копирует, но сильнее перерасходует память; 1.5 даёт хороший баланс и возможность переиспользовать освобождённые блоки памяти.
// HotSpot OpenJDK, упрощённо:
int newCapacity = oldCapacity + (oldCapacity >> 1); // ~1.5x
elementData = Arrays.copyOf(elementData, newCapacity);
Почему add амортизированно O(1)
Отдельное копирование при росте стоит O(n), но происходит редко: между расширениями добавляется пропорционально текущему размеру элементов. Суммарная стоимость N добавлений — O(N), значит на одно добавление в среднем O(1) — это и есть амортизированная оценка.
Если финальный размер известен заранее, стоит задать начальную ёмкость new ArrayList<>(expectedSize) или вызвать ensureCapacity — это исключает серию перекопирований.
Вставка и удаление в середину
add(index, e) и remove(index) сдвигают «хвост» массива через System.arraycopy, поэтому стоят O(n). Это плата за непрерывное хранение: чтобы вставить в середину, всё правее нужно подвинуть.
Удаление последнего элемента — O(1). Для массового удаления по условию используют removeIf — он делает один проход вместо многократного сдвига.
Нюансы
ArrayList не потокобезопасен, итератор fail-fast (через modCount). После большого роста и последующего сжатия данных память не возвращается автоматически — есть trimToSize().
subList возвращает view на исходный список, а не копию: структурное изменение оригинала ломает view. Это частый источник тонких багов.
Как отвечать на собеседовании
Объясните различие size/capacity, рост в 1.5× и амортизированную O(1) (через суммарную стоимость), назовите O(n) на вставку в середину из-за arraycopy и упомяните задание начальной ёмкости как оптимизацию. Это сразу показывает понимание, а не зубрёжку.