Какова сложность вставки элемента в середину LinkedList

Вставка элемента в середину `LinkedList` в среднем имеет сложность **O(n)**, так как требует прохода до нужной позиции. **Пример:** ```java LinkedList list = new LinkedList<>(); list.add("A"); list.add("B"); list.add(1, "X"); // Вставка в середину (O(n)) ``` **Нюансы:** - Если вставка происходит по индексу 0 или `list.size()`, сложность **O(1)** (т.к. `LinkedList` хранит ссылки на голову и хвост). - В отличие от `ArrayList`, `LinkedList` не требует сдвига элементов, но поиск позиции остаётся линейным.