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

Временная сложность вставки элемента в LinkedList зависит от того, куда он вставляется:

• В начало или конец списка: O(1)
• В середину списка: O(N), где N - количество элементов в списке.

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