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

Ну слушай, вот сидишь ты такой, пишешь на Java, и думаешь: "А возьму-ка я LinkedList, он же крутой, вставки-удаления за O(1), красота!" А потом тебе вдруг надо найти в нём какой-нибудь элемент, не по индексу, а по значению. И тут начинается пиздец, Карл.

Потому что этот LinkedList — он как тот немой Герасим из рассказа, только вместо "Му-му" он мычит "Ссылка-ссылка". Элементы там разбросаны по памяти, как охуевшие овцы по полю, и чтобы найти одну конкретную овцу по имени "Боря", тебе придётся обойти всё стадо, начиная с первой. Это и есть тот самый O(n) в худшем и среднем случае. Если элемент в хвосте — проебёшься по всему списку. Если в начале — повезло. Но в среднем — нихуя не повезло.

Вот смотри, как это выглядит в коде, тут всё честно:

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

Вызвал indexOf("B") — а под капотом, блядь, начинается линейный обход: "Ты 'B'? Нет? Иди нахуй. Ты 'B'? Да? Ну наконец-то, ебанашка!"

Так что, чувак, рекомендации простые, как три копейки:

• Если тебе постоянно надо тыкать пальцем в элемент по номеру — выкинь этот LinkedList в пизду и бери ArrayList. Там доступ по индекту — O(1), то есть моментально, как хуй в сало.
• Если поиск по значению — твоя основная головная боль, а вставки/удаления не так часты — тут LinkedList вообще не катит. Смотри в сторону HashSet (поиск в среднем O(1), ёпта!) или TreeSet (O(log n), упорядоченный). Вот это — инструменты, а не мартышлюшка со ссылками.

Короче, выбирай структуру данных с умом, а не потому что название понравилось. А то получится как в той истории: "Муму-муму", а в итоге — утопил производительность, блядь.