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

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

val list = LinkedList<String>().apply {
    add("A")
    add("B")
    add("C")
}
val index = list.indexOf("B") // O(n) - линейный поиск

Для частых операций поиска лучше использовать ArrayList (доступ по индексу за O(1)) или HashSet (поиск за O(1)).