Всегда ли добавление элемента в ArrayList имеет сложность O(1)?

Не всегда.

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

// Пример добавления в конец
List<String> list = new ArrayList<>();
list.add("element1"); // O(1) в типичном случае

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

// Пример добавления, вызывающего увеличение емкости
List<Integer> list = new ArrayList<>(5); // Изначальная емкость
for (int i = 0; i < 5; i++) {
    list.add(i); // O(1)
}
list.add(5); // Здесь может произойти увеличение емкости, что вызовет O(n)

Кроме того, добавление элемента не в конец ArrayList всегда имеет сложность O(n). Это связано с тем, что все элементы, расположенные после места вставки, должны быть сдвинуты вправо, чтобы освободить место для нового элемента.

// Пример добавления не в конец
List<String> list = new ArrayList<>(List.of("a", "c"));
list.add(1, "b"); // O(n), так как элемент "c" нужно сдвинуть

Суммируя: