Какова временная сложность операции удаления элемента из середины массива, реализованного через ArrayList?

В Java класс ArrayList реализован на основе динамического массива. При удалении элемента из середины массива происходит сдвиг всех последующих элементов на одну позицию влево, чтобы заполнить образовавшуюся «дыру».

Поэтому временная сложность операции удаления элемента из середины ArrayList — O(n), где n — количество элементов после удаляемого.

Пример:

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
list.remove(2); // удаляет элемент с индексом 2 (число 3)
// элементы 4 и 5 сдвигаются влево

Удаление с конца списка — операция O(1), так как сдвиг не требуется.