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

Вставка элемента в середину LinkedList — это операция O(n), где n — количество элементов в списке.

Процесс вставки по индексу add(index, element):

1. Поиск позиции (O(n)): Происходит обход списка с головы или хвоста (в зависимости от того, какая половина ближе) для нахождения узла по заданному индексу.
2. Вставка (O(1)): После нахождения узла-предшественника создаётся новый узел, и перенаправляются 4 ссылки:
   • newNode.prev = predecessor
   • newNode.next = successor
   • predecessor.next = newNode
   • successor.prev = newNode

Пример кода:

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "C"));
// Вставка "B" по индексу 1 (между "A" и "C")
list.add(1, "B");
System.out.println(list); // [A, B, C]

Вывод: LinkedList эффективен для частых вставок/удалений в уже известной позиции (например, при работе с итератором ListIterator.add()), но не для случайного доступа по индексу.