Вопрос проверяет понимание влияния структуры данных на стоимость операций вставки.
Вставка в середину ArrayList выполняется за O(n).
В LinkedList вставка элемента после нахождения позиции выполняется за O(1).
Однако поиск позиции в LinkedList тоже занимает O(n).
Итоговая сложность операций на практике сопоставима.
Разница заключается в копировании элементов и работе со ссылками.
Перед сравнением важно разделить операцию вставки на логические этапы.
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), но по разным причинам: сдвиг элементов против обхода списка.