Quelle est la complexité temporelle lors de la recherche d'un élément par valeur dans une liste chaînée (LinkedList) ?

Dans une liste chaînée (LinkedList), rechercher un élément par sa valeur nécessite une traversée séquentielle des éléments, en commençant par la tête de la liste, jusqu'à ce que l'élément recherché soit trouvé ou que la liste soit terminée. Par conséquent, la complexité temporelle de la recherche est O(n), où n est le nombre d'éléments dans la liste.

Exemple en Java:

LinkedList<String> list = new LinkedList<>();
list.add("pomme");
list.add("banane");
list.add("cerise");

boolean contientBanane = list.contains("banane"); // Parcours jusqu'à "banane"

La méthode contains() parcourt les éléments de manière séquentielle, ce qui explique sa complexité linéaire.