Почему функция удаления Java ArrayList, кажется, стоит так мало?

У меня есть функция, которая управляет очень большим списком, превышающим примерно 250 000 элементов. Для большинства этих элементов он просто заменяет элемент в позиции x. Однако около 5% из них он должен удалить их из списка.

Использование LinkedList казалось наиболее очевидным решением, позволяющим избежать дорогостоящего удаления. Однако, естественно, доступ к LinkedList по индексу со временем становится все медленнее. Стоимость здесь составляет минуты (и их много).

Использование Iterator поверх этого LinkedList также является дорогостоящим, поскольку мне, кажется, нужна отдельная копия, чтобы избежать проблем с параллелизмом Iterator при редактировании этого списка. Стоимость здесь составляет минуты.

Однако здесь я немного взорван. Если я перейду на ArrayList, он запустится почти мгновенно.

Для списка с 297515 элементами удаление 11958 элементов и изменение всего остального занимает 909 мс. Я проверил, что полученный список действительно имеет размер 285557, как и ожидалось, и содержит необходимую мне обновленную информацию.

Почему это так быстро? Я посмотрел на источник ArrayList в JDK6, и, похоже, он использует функцию копирования массива, как и ожидалось. Мне хотелось бы понять, почему ArrayList здесь так хорошо работает, когда здравый смысл, кажется, указывает на то, что массив для этой задачи - ужасная идея, требующая перемещения нескольких сотен тысяч элементов.