Jaká je časová složitost při hledání prvku podle hodnoty v spojovaném seznamu (LinkedList)?

V spojovaném seznamu (LinkedList) vyžaduje hledání prvku podle hodnoty sekvenční průchod prvky, začínající od hlavy seznamu, dokud se nenajde požadovaný prvek nebo seznam neskončí. Proto je časová složitost hledání O(n), kde n je počet prvků v seznamu.

Příklad v Javě:

LinkedList<String> list = new LinkedList<>();
list.add("jablko");
list.add("banán");
list.add("třešeň");

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

Metoda contains() prochází prvky sekvenčně, což vysvětluje její lineární složitost.