Kokia yra laiko sudėtingumas ieškant elemento pagal reikšmę susietame sąraše (LinkedList)?

Sujungtame sąraše (LinkedList) elemento paieška pagal reikšmę reikalauja sekvenčio elementų perėjimo, pradedant nuo sąrašo pradžios, kol bus rastas norimas elementas arba sąrašas pasibaigs. Todėl paieškos laiko sudėtingumas yra O(n), kur n yra elementų skaičius sąraše.

Pavyzdys Java kalba:

LinkedList<String> list = new LinkedList<>();
list.add("obuolys");
list.add("bananas");
list.add("vyšnia");

boolean turiBanana = list.contains("bananas"); // Perėjimas iki "bananas"

contains() metodas pereina per elementus sekvenškai, kas paaiškina jo linijinį sudėtingumą.