Какая сложность операции удаления из ArrayList

Удаление из ArrayList имеет временную сложность O(n) в худшем случае (удаление первого элемента), так как требует сдвига всех последующих элементов. В лучшем случае (удаление последнего элемента) — O(1), так как сдвиг не нужен.

val list = arrayListOf(1, 2, 3, 4)
list.removeAt(0) // O(n) — сдвиг элементов 2, 3, 4
list.removeAt(list.size - 1) // O(1) — просто удаление

Если часто требуется удаление, лучше использовать LinkedList (удаление за O(1)), но учти, что у него другие trade-offs (например, доступ по индексу O(n)).