Сложность добавления элемента в ArrayList в среднем случае составляет O(1).
Это достигается за счет использования динамического массива, и добавление происходит в конец списка.
javaОднако, в случае, если внутренний массив ArrayList заполнен, требуется операция увеличения его размера (resize). Это включает создание нового, большего массива и копирование всех существующих элементов в новый массив. Сложность этой операции составляет O(n), где n — текущий размер списка.
javaЕсли элемент добавляется не в конец списка (методом add(int index, E element)), а в середину или начало, то требуется сдвиг всех последующих элементов на одну позицию вправо. Сложность этой операции составляет O(n), где n — количество элементов, которые необходимо сдвинуть.
javaТаким образом, сложность добавления элемента в ArrayList зависит от места добавления и необходимости resize:
| Операция добавления | Средний случай | Худший случай (при resize или добавлении не в конец) |
|---|---|---|
add(E element) (в конец) | O(1) | O(n) |
add(int index, E element) | O(n) | O(n) |