Comment évaluer l'efficacité de la recherche d'un élément dans la structure de données LinkedList?

La recherche d'un élément dans la structure de données LinkedList est évaluée en moyenne et dans le pire des cas comme O(n), où n est le nombre d'éléments dans la liste.

Cela est dû au fait que LinkedList ne supporte pas l'accès direct aux éléments par index, et pour rechercher, il faut parcourir séquentiellement les éléments à partir de la tête de la liste jusqu'à ce que l'élément recherché soit trouvé ou que la fin soit atteinte.

Ainsi, l'efficacité de la recherche dans LinkedList est nettement inférieure à celle des tableaux ou des listes avec support de l'indexation (par exemple, ArrayList en Java), où la recherche par index est O(1).