Kui suur on ajakulu keerukus otsides elementi väärtuse järgi seotud nimekirjas (LinkedList)?

LinkedList-s (Seotud nimekirja) elementide otsimine väärtuse järgi nõuab elementide järjestikust läbimist, alustades nimekirja algusest, kuni leitakse soovitud element või nimekiri lõpeb. Seetõttu on otsingu ajakompleksus O(n), kus n on nimekirja elementide arv.

Näide Java-s:

LinkedList<String> list = new LinkedList<>();
list.add("õun");
list.add("banaan");
list.add("kirss");

boolean sisaldabBanaani = list.contains("banaan"); // Läbimine kuni "banaan"

contains() meetod läbib elemendid järjestikku, mis selgitab selle lineaarset keerukust.