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

Временная сложность зависит от позиции вставки:

• O(1) для вставки в начало (addFirst()) или конец (addLast()) списка. Операция сводится к обновлению ссылок у головного (head) или хвостового (tail) узла.
• O(n) для вставки в произвольную позицию по индексу (add(int index, E element)). Требуется линейный обход для нахождения узла-предшественника.

Пример:

LinkedList<String> list = new LinkedList<>();
list.add("A");        // O(1) - вставка в конец
list.addFirst("B");   // O(1) - вставка в начало
list.add(1, "C");     // O(n) - вставка в середину (требуется обход до индекса 1)

Почему? LinkedList реализован как двусвязный список. Прямой доступ по индексу отсутствует, поэтому нахождение нужной позиции для вставки "в середину" требует последовательного прохода от начала списка.