Какая сложность вставки элемента в середину ArrayList и LinkedList и почему она различается?

Question

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

YeaHub · Accepted Answer

Перед сравнением важно разделить операцию вставки на логические этапы.Вставка в ArrayListПроцесс состоит из:Поиска индекса (O(1), если индекс известен).Сдвига всех элементов вправо.Записи нового значения.Пример:list.add(index, value);
Сдвиг элементов:требует копированиязатрагивает до n / 2 элементов в среднемИтог:сложность O(n)Вставка в LinkedListОперация включает:Поиск нужного узла (O(n)).Перенастройку ссылок (O(1)).list.add(index, value);
Если узел уже найден:вставка происходит мгновеннобез копирования данныхПочему на практике разница небольшаяВажно учитывать:В LinkedList дорогой доступ к позиции.В ArrayList быстрый доступ, но дорогой сдвиг.Кэш-память процессора лучше работает с массивами.Краткий выводВставка в середину и ArrayList, и LinkedList в итоге имеет сложность O(n), но по разным причинам: сдвиг элементов против обхода списка.