Comment l'ajout d'un élément dans ArrayList est-il effectué dans le pire scénario d'exécution ?

При добавлении элемента в ArrayList в Java в наихудшем сценарии происходит следующее:

1. Проверка вместимости: Если внутренний массив ArrayList заполнен, необходимо увеличить его размер.
2. Расширение массива: Создаётся новый массив большего размера (обычно в 1.5–2 раза больше), и все элементы копируются из старого массива в новый.
3. Добавление элемента: Новый элемент помещается в расширенный массив.

Из-за копирования всех элементов операция расширения массива занимает время O(n), где n — количество элементов в списке. Поэтому в наихудшем случае добавление элемента — это операция с линейной сложностью.

Пример:

ArrayList<Integer> list = new ArrayList<>(2);
list.add(1);
list.add(2);
// При следующем добавлении внутренний массив расширится
list.add(3); // Здесь происходит копирование элементов в новый массив

Таким образом, хотя средняя амортизированная сложность добавления — O(1), наихудший случай — O(n) из-за необходимости расширения внутреннего массива.