Как определить скорость поиска элемента в связном списке?

Скорость поиска элемента в связном списке обычно оценивается как O(n), где n — количество элементов в списке. Это связано с тем, что для поиска конкретного элемента приходится последовательно проходить узлы списка, начиная с головы, пока не будет найден нужный элемент или достигнут конец списка.

Пример на Java для поиска элемента в односвязном списке:

class Node {
    int value;
    Node next;
    Node(int value) { this.value = value; }
}

public boolean contains(Node head, int target) {
    Node current = head;
    while (current != null) {
        if (current.value == target) {
            return true;
        }
        current = current.next;
    }
    return false;
}

Здесь в худшем случае придется пройти весь список, что и определяет линейную сложность поиска.