Wat is de tijdcomplexiteit bij het zoeken van een element op waarde in een gekoppelde lijst (LinkedList)?

In een gekoppelde lijst (LinkedList) vereist het zoeken naar een element op waarde een sequentiële doorloop van de elementen, beginnend bij de kop van de lijst, totdat het gewenste element is gevonden of de lijst eindigt. Daarom is de tijdcomplexiteit van de zoekactie O(n), waarbij n het aantal elementen in de lijst is.

Voorbeeld in Java:

LinkedList<String> list = new LinkedList<>();
list.add("appel");
list.add("banaan");
list.add("kers");

boolean bevatBanaan = list.contains("banaan"); // Doorloop tot "banaan"

De methode contains() doorloopt de elementen sequentieel, wat de lineaire complexiteit verklaart.