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

O(n) в худшем и среднем случае, где n — количество элементов в списке.

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

Пример на Java:

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");
// Метод indexOf выполняет линейный поиск
int index = list.indexOf("B"); // В худшем случае проверит все n элементов

Рекомендации:

• Если частой операцией является поиск по индексу — используйте ArrayList (O(1)).
• Если нужен быстрый поиск по значению — рассмотрите HashSet (O(1) в среднем) или TreeSet (O(log n)).