Wie ist die zeitliche Komplexität beim Entfernen eines Elements aus der Mitte eines Arrays, das mit ArrayList implementiert ist?

В 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), так как сдвиг не требуется.