Qual é a complexidade de tempo na busca de um elemento por valor numa lista ligada (LinkedList)?

Numa lista ligada (LinkedList), procurar um elemento pelo valor requer uma passagem sequencial pelos elementos, começando pela cabeça da lista, até encontrar o elemento desejado ou chegar ao final da lista. Portanto, a complexidade temporal da busca é O(n), onde n é o número de elementos na lista.

Exemplo em Java:

LinkedList<String> list = new LinkedList<>();
list.add("maçã");
list.add("banana");
list.add("cereja");

boolean containsBanana = list.contains("banana"); // Passagem até "banana"

O método contains() percorre os elementos sequencialmente, o que explica sua complexidade linear.