Какая структура данных обеспечит более быстрый вставку элемента в середину: ArrayList или LinkedList?

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

Причина в том, что:

• В ArrayList вставка в середину требует сдвига всех последующих элементов, что даёт временную сложность O(n).
• В LinkedList достаточно изменить ссылки соседних узлов, чтобы вставить элемент, что занимает O(1) при наличии ссылки на нужный узел. Однако поиск этого узла занимает O(n), если ссылка отсутствует.

Если у вас есть ссылка на позицию вставки, LinkedList быстрее; если нет, то оба варианта примерно одинаковы по времени из-за необходимости поиска.

LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
ListIterator<Integer> it = list.listIterator(1); // позиция вставки
it.add(99); // вставка в середину