Какое худшее время работы метода add() для LinkedList

Худшее время — O(N). Метод add(int index, E element) с указанием позиции требует сначала найти узел на позиции index, что занимает O(N), а затем выполнить вставку за O(1).

Метод add(E element) без индекса (добавление в конец) всегда работает за O(1), потому что LinkedList хранит прямую ссылку на последний узел. Аналогично, addFirst() и addLast() работают за O(1).

Оптимизация: при поиске позиции LinkedList определяет, ближе ли index к началу или концу списка, и начинает обход с ближайшего края. Поэтому worst case — вставка в середину (N/2 переходов).

На собеседовании: уточните, о каком варианте add() идет речь. Без индекса — O(1), с индексом — O(N). Это важное различие.