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