Какое худшее время работы метода contains() для элемента, который есть в LinkedList

Худшее время — O(N). Метод contains() в LinkedList выполняет линейный поиск: последовательно обходит узлы от начала списка, вызывая equals() для каждого элемента, пока не найдет совпадение.

В худшем случае искомый элемент находится в последней позиции списка, и метод пройдет все N узлов. Оптимизация невозможна без дополнительных структур данных, потому что LinkedList не поддерживает произвольный доступ и не сортирован.

На собеседовании: ответ — O(N). Если на собеседовании спрашивают дальше, объясните, что ускорить поиск можно только с помощью дополнительного индекса (например, HashSet для проверки наличия).