Какова сложность вставки элемента в начало ArrayList, если capacity достаточна?

Сложность операции O(n), где n — текущий размер списка. Все существующие элементы должны быть сдвинуты.

Процесс под капотом (add(0, element)):

1. Проверка, что size + 1 <= capacity (расширения не требуется).
2. System.arraycopy() копирует весь массив elementData на одну позицию вправо.
3. Запись нового элемента в индекс 0.
4. Инкремент size.

Пример:

ArrayList<Integer> list = new ArrayList<>(5); // capacity=5
list.addAll(Arrays.asList(10, 20, 30)); // size=3
list.add(0, 5); // Вставка в начало
// Шаги:
// 1. arraycopy([10,20,30,null,null], 0, [10,20,30,null,null], 1, 3)
// 2. Результат: [10,20,30,null,null] -> [10,10,20,30,null]
// 3. elementData[0] = 5
// Итог: [5,10,20,30,null]

Сравнение: Вставка в конец (add(element)) имеет сложность O(1) (амортизированную).