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

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

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

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

• В LinkedList элементы связаны ссылками, поэтому достаточно изменить ссылки соседних узлов, чтобы вставить новый элемент, что занимает O(1) для самой вставки, но поиск позиции для вставки — O(n).

Таким образом, если у вас уже есть ссылка на нужный узел, вставка в LinkedList быстрее. Но если нужно сначала найти позицию, то по времени это примерно одинаково.

Пример:

List<String> list = new LinkedList<>();
// добавляем элементы
list.add("a");
list.add("b");
list.add("c");

// вставляем в середину
list.add(1, "x");