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

O(1).

Вставка элемента в LinkedList по индексу требует итерации от начала или конца списка (в зависимости от того, что ближе к индексу) до нужной позиции, что имеет сложность O(n). Однако, если у нас есть ссылка на узел перед местом вставки (например, при вставке в начало или конец), операция занимает O(1).

// Вставка в начало
LinkedList<String> list = new LinkedList<>();
list.addFirst("элемент"); // O(1)

// Вставка в конец
list.addLast("другой элемент"); // O(1)

// Вставка по индексу (требует поиска узла)
list.add(1, "в середине"); // O(n) в худшем случае, O(1) для 0 или size()