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

Вставка элемента в середину массива ArrayList в Java имеет временную сложность O(n), где n — количество элементов в списке.

Причина в том, что ArrayList реализован на основе обычного массива. При вставке в середину необходимо:

1. Освободить место для нового элемента, сдвинув все элементы, начиная с позиции вставки, на один индекс вправо.
2. Записать новый элемент в освободившуюся позицию.

Сдвиг элементов — операция, требующая копирования примерно половины элементов массива (в среднем n/2), что даёт линейную сложность.

Пример:

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
list.add(2, 99); // вставляем 99 на позицию с индексом 2
// После вставки: [1, 2, 99, 3, 4, 5]

Если вставлять элемент в конец списка, сложность будет амортизированно O(1), так как сдвиг не требуется.