Для ArrayList или для LinkedList операция добавления элемента в середину медленнее

В теории оба списка тратят O(N) на вставку в середину, но по разным причинам. ArrayList тратит время на сдвиг элементов правее позиции вставки через System.arraycopy(), а LinkedList — на поиск узла на нужной позиции (обход от начала или конца).

На практике вставка в середину обычно быстрее для ArrayList, несмотря на то, что теоретическая сложность одинакова. Причины:

• System.arraycopy() — это нативная операция, оптимизированная под процессор, копирующая блоки памяти.
• Последовательное расположение элементов ArrayList в памяти обеспечивает cache-friendly доступ.
• LinkedList при обходе следует по ссылкам на объекты, разбросанные по heap, что приводит к cache miss.

В худшем случае (расширение массива + сдвиг) ArrayList может быть медленнее LinkedList, но это редкая ситуация.

На собеседовании: скажите, что в теории одинаково O(N), но на практике ArrayList обычно быстрее из-за System.arraycopy() и cache locality. В худшем случае (расширение массива) может проиграть.