Какова сложность добавления элемента в ArrayList?

Сложность добавления элемента в ArrayList в среднем случае составляет O(1).

Это достигается за счет использования динамического массива, и добавление происходит в конец списка.

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

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

// Пример, где может сработать resize
List<Integer> numbers = new ArrayList<>(3); // Изначальная емкость 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Здесь может произойти resize - O(n)

Если элемент добавляется не в конец списка (методом add(int index, E element)), а в середину или начало, то требуется сдвиг всех последующих элементов на одну позицию вправо. Сложность этой операции составляет O(n), где n — количество элементов, которые необходимо сдвинуть.

// Добавление в начало списка
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Добавление в начало - O(n)

Таким образом, сложность добавления элемента в ArrayList зависит от места добавления и необходимости resize: