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

Сложность зависит от позиции вставки:

• O(1) — если известен узел, после/перед которым происходит вставка (например, в начало или конец списка).
• O(n) — если вставка происходит по индексу, так как требуется линейный поиск нужной позиции.

Примеры:

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

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