Какая временная сложность доступа к элементу связного списка (linked list)?

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

// Реализация доступа к узлу по индексу в Node.js
class ListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

function getNodeAtIndex(head, index) {
  let currentNode = head;
  let currentIndex = 0;

  while (currentNode !== null) {
    if (currentIndex === index) {
      return currentNode; // Найден нужный узел
    }
    currentNode = currentNode.next;
    currentIndex++;
  }
  return null; // Индекс выходит за пределы списка
}

// Пример использования
const list = new ListNode(1, new ListNode(2, new ListNode(3)));
const node = getNodeAtIndex(list, 2); // Чтобы добраться до узла со значением 3, нужно пройти через два предыдущих узла.
console.log(node?.value); // 3

Почему O(n)? В худшем случае (доступ к последнему элементу) необходимо пройти все n узлов. Это основное отличие от массивов (Array в JavaScript), где доступ по индексу выполняется за O(1) благодаря вычислению смещения в памяти. Связные списки полезны для частых операций вставки/удаления в начале или середине списка, где их сложность O(1) или O(n) для доступа + O(1) для изменения ссылок может быть выгоднее, чем O(n) для сдвига элементов в массиве.