Ako sa hodnotí efektívnosť vyhľadávania prvku v dátovej štruktúre LinkedList?

Vyhľadávanie prvku v dátovej štruktúre LinkedList sa odhaduje ako O(n) v priemere aj v najhoršom prípade, kde n je počet prvkov v zozname.

Dôvodom je, že LinkedList nepodporuje priame prístupy k prvkom podľa indexu, a na vyhľadanie je potrebné sekvenčne prejsť prvky od hlavy zoznamu, kým nenájdete požadovaný prvok alebo nedosiahnete koniec.

Preto je efektívnosť vyhľadávania v LinkedList podstatne nižšia ako v poliach alebo zoznamoch s podporou indexovania (napríklad ArrayList v Jave), kde je vyhľadávanie podľa indexu O(1).