¿Cuál es la complejidad temporal al buscar un elemento por valor en una lista enlazada (LinkedList)?

En una lista enlazada (LinkedList), buscar un elemento por valor requiere recorrer secuencialmente los elementos, comenzando desde la cabeza de la lista, hasta encontrar el elemento deseado o llegar al final de la lista. Por lo tanto, la complejidad temporal de la búsqueda es O(n), donde n es la cantidad de elementos en la lista.

Ejemplo en Java:

LinkedList<String> list = new LinkedList<>();
list.add("manzana");
list.add("banana");
list.add("cereza");

boolean contieneBanana = list.contains("banana"); // Recorrido hasta "banana"

El método contains() recorre los elementos de forma secuencial, lo que determina su complejidad lineal.