Какова временная сложность при поиске элемента по значению в связном списке (LinkedList)?

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

Пример на Java:

LinkedList<String> list = new LinkedList<>();
list.add("apple");
list.add("banana");
list.add("cherry");

boolean containsBanana = list.contains("banana"); // Проход по элементам до "banana"

Метод contains() перебирает элементы последовательно, что и обуславливает линейную сложность.