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

Поиск элемента в связном списке (односвязном или двусвязном) имеет линейную сложность O(n) в худшем и среднем случаях.

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

• Худший случай: O(n) — элемент находится в конце списка или отсутствует.
• Средний случай: O(n) — в среднем нужно будет пройти n/2 элементов.
• Лучший случай: O(1) — искомый элемент является первым в списке.

Пример поиска в односвязном списке на Go:

type Node struct {
    Value int
    Next  *Node
}

// Search ищет целевое значение в списке, начиная с узла head.
func Search(head *Node, target int) bool {
    current := head
    for current != nil {
        if current.Value == target {
            return true // Элемент найден
        }
        current = current.Next
    }
    return false // Элемент не найден
}