Какая будет сложность операции вставки в середину LinkedList

Вставка в середину `LinkedList` имеет сложность **O(n)**, где n — количество элементов. Это связано с тем, что для вставки элемента в середину списка необходимо пройти от начала (или конца) до нужной позиции, что требует линейного времени. Однако, если у нас уже есть ссылка на узел (`Node`), вставка выполняется за **O(1)**. Пример: ```java LinkedList list = new LinkedList<>(); list.add(1); list.add(2); list.add(3); // Вставка в середину (индекс 1) – O(n) list.add(1, 99); ``` Для сравнения, `ArrayList` вставка в середину также **O(n)** из-за сдвига элементов, но с более высокими накладными расходами из-за копирования массива.