Какая сложность вставки у ArrayList?

Сложность вставки в ArrayList зависит от позиции вставки:

• Вставка в конец: амортизированная сложность O(1), так как обычно элемент просто добавляется в конец массива. При переполнении массива происходит перераспределение памяти (копирование в новый массив большего размера), что занимает O(n), но происходит редко.
• Вставка в середину или начало: требует сдвига всех последующих элементов вправо, поэтому сложность O(n) в худшем случае.

Пример:

• Если у вас есть ArrayList из 100 элементов и вы вставляете элемент в позицию 50, то элементы с 50 по 99 сдвинутся на одну позицию вправо, что занимает O(n) операций.

Таким образом, вставка в ArrayList эффективна только в конце, а вставка в произвольную позицию — затратна по времени.