Ответ
В среднем — нет (амортизированная O(1)), но в худшем случае — да (O(n)).
- Большинство операций
add(E element)выполняются за O(1), так как элемент добавляется в конец внутреннего массива. - Когда внутренний массив заполнен, происходит операция resize (увеличение capacity): создается новый массив большего размера (обычно
старыйCapacity * 1.5), и все существующие элементы копируются в него. Эта операция имеет сложность O(n).
Практический пример:
// ArrayList с начальной capacity = 2
ArrayList<Integer> list = new ArrayList<>(2);
list.add(1); // O(1) - добавление в массив
list.add(2); // O(1) - массив заполнен
list.add(3); // O(n)!
// Происходит resize: capacity становится 3, элементы 1 и 2 копируются.Рекомендация: Если известен ожидаемый размер коллекции, задайте его в конструкторе ArrayList(int initialCapacity), чтобы минимизировать количество операций копирования.