¿Qué estructura de datos proporcionará una inserción más rápida en el medio: ArrayList o 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); // вставка в середину