Какая средняя и худшая временная сложность добавления элемента в ArrayList

Что проверяют

Знаете ли вы, как растёт ArrayList, и отличаете ли амортизированную сложность от средней. Следом спрашивают, во сколько раз увеличивается массив и как избежать лишних копирований.

Как отвечать

• add(e) в конец: амортизированно O(1), в худшем случае O(n). Пока в массиве elementData есть место, элемент записывается в следующую ячейку;
• расширение: когда место кончилось, создаётся новый массив, старый копируется через Arrays.copyOf. Новая ёмкость в полтора раза больше: oldCapacity + (oldCapacity >> 1), то есть 10 превращается в 15, 15 в 22;
• начальная ёмкость: new ArrayList<>() не выделяет массив сразу, он создаётся на первом add размером 10. Конструктор new ArrayList<>(n) выделяет n ячеек заранее;
• add(index, e) в середину: O(n) даже без расширения, потому что хвост сдвигается через System.arraycopy. Вставка в начало самая дорогая.

Почему амортизированная, а не средняя. Средняя подразумевает вероятность по входным данным, а амортизированная это гарантия для любой последовательности операций. Рост геометрический, поэтому за n добавлений суммарно копируется не больше 3n элементов, и на одну вставку приходится константа. Если бы массив рос на фиксированное число ячеек, суммарно вышло бы O(n²).

Практические выводы: если размер известен, передайте его в конструктор или вызовите ensureCapacity, это убирает копирования. При удалении массив не сжимается, лишнюю память возвращает только trimToSize. На очень больших списках отдельная вставка с расширением копирует миллионы ссылок, и это заметная пауза в коде с требованиями к задержкам.

Где спотыкаются

Говорят, что массив удваивается. В ArrayList множитель полтора, удвоение это поведение Vector по умолчанию.

Называют сложность просто средней O(1) и не могут объяснить, откуда она берётся, без подсчёта суммы копирований.

Забывают про вставку по индексу и отвечают O(1) для add(0, e), хотя сдвиг всего массива стоит O(n).