ArrayList.

При удалении элемента из середины списка:

ArrayList: Требует смещения всех последующих элементов, что в худшем случае (при удалении первого элемента) занимает время $О(n)$ , где $n$ — количество элементов. Однако, в среднем, операция остается $О(n)$ , так как нужно сместить только половину элементов. Фактическая производительность часто выше из-за лучшей локальности данных.
LinkedList: Требует итерации по элементам до нахождения нужного узла ( $O(n)$ в худшем случае, если итерация начинается с начала или конца). После нахождения узла удаление занимает $О(1)$ .

Несмотря на то, что удаление самого узла в LinkedList быстрее, поиск узла до удаления делает общую операцию в среднем медленнее, чем в ArrayList.

java

Результаты бенчмарка показывают, что для удаления элемента из середины, ArrayList, как правило, быстрее, несмотря на теоретическую сложность сдвига. Это связано с тем, что поиск элемента по индексу в LinkedList ( $O(n)$ ) выполняется медленнее, чем сдвиг в ArrayList.

java

В итоге, для операции удаления из середины, если вы знаете индекс, ArrayList часто является более предпочтительным выбором из-за более быстрой операции доступа по индексу, что компенсирует затраты на сдвиг.

Что лучше использовать: ArrayList или LinkedList, если я хочу удалить элемент из середины списка?