Bağlantılı listedeki (LinkedList) bir öğeyi değere göre aramanın zaman karmaşıklığı nedir?

Bağlantılı liste (LinkedList) içinde bir öğeyi değere göre aramak, listenin başından başlayarak öğeleri sıralı şekilde dolaşmayı gerektirir, ta ki istenen öğe bulunana kadar veya liste sona erene kadar. Bu nedenle, aramanın zaman karmaşıklığı O(n)'dir, burada n listedeki öğe sayısıdır.

Java'da örnek:

LinkedList<String> list = new LinkedList<>();
list.add("elma");
list.add("muz");
list.add("kiraz");

boolean containsMuz = list.contains("muz"); // "muz"'a kadar geçer

contains() metodu öğeleri sıralı şekilde dolaşır, bu da onun doğrusal karmaşıklığını açıklar.