Aká je časová zložitosť pri hľadaní prvku podľa hodnoty v spojovom zozname (LinkedList)?

V spojenom zozname (LinkedList) vyžaduje vyhľadávanie prvku podľa hodnoty sekvenčné prechádzanie prvkov, začínajúc od hlavy zoznamu, až kým sa nenájde požadovaný prvok alebo zoznam neskončí. Preto je časová zložitosť vyhľadávania O(n), kde n je počet prvkov v zozname.

Príklad v Jave:

LinkedList<String> list = new LinkedList<>();
list.add("jablko");
list.add("banán");
list.add("čerešňa");

boolean obsahujeBanán = list.contains("banán"); // Prechod až k "banán"

Metóda contains() prechádza prvky sekvenčne, čo vysvetľuje jej lineárnu zložitosť.