Что хотят услышать интервьюеры:

В связном списке поиск элемента выполняется за линейное время, потому что в худшем случае приходится пройти все узлы по одному. В терминах асимптотики это O(n). Для оценки времени важно смотреть на количество посещённых элементов, а не на размер памяти или доступ по индексу.

Определение:

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

Пример использования:

Например, если в списке 1 → 4 → 7 → 9 нужно найти 7, алгоритм проверит 1, затем 4, затем 7 и остановится. Если искомого элемента нет, он пройдёт весь список до конца.

function findInLinkedList(head, target) {
  let current = head;
  let steps = 0;

  while (current !== null) {
    steps++;
    if (current.value === target) {
      return { found: true, steps };
    }
    current = current.next;
  }

  return { found: false, steps };
}

Пояснение кода:

Код не требует отдельного вычисления времени через performance или Date.now(), потому что здесь оценивается не реальная длительность, а алгоритмическая сложность.
Шаги такие:

Начинаем с головы списка.
Идём по узлам по цепочке next.
На каждом узле сравниваем значение с искомым.
Если нашли — завершаем поиск.
Если дошли до null, элемента в списке нет.
Количество проверок в худшем случае равно числу узлов, поэтому сложность — O(n).

Ключевые моменты:

Поиск в связном списке обычно имеет сложность O(n).
В худшем случае нужно проверить все элементы.
В среднем случае тоже нет быстрого доступа, как у массива по индексу.
Для оценки времени считают число проходов по узлам, а не фактические миллисекунды.
Если нужен быстрый поиск по значению, часто используют другие структуры данных, например Map или Set.

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