re:re:actable
Урок 023 минуты чтения

Что такое linked list?

На этой странице
Кратко

Linked list - структура данных из узлов, где каждый узел хранит значение и ссылку на следующий узел. В отличие от массива, она не дает быстрого доступа по индексу, но позволяет эффективно вставлять и удалять узлы, если ссылка на место уже известна.

Вопрос

Что такое linked list, чем он отличается от массива и как его разворачивать?

Узел списка

type ListNode<T> = {
  value: T
  next: ListNode<T> | null
}

Пример:

10 -> 20 -> 30 -> null

Обход

function toArray<T>(head: ListNode<T> | null): T[] {
  const result: T[] = []
  let current = head
 
  while (current) {
    result.push(current.value)
    current = current.next
  }
 
  return result
}

Time O(n).

Разворот linked list

function reverse<T>(head: ListNode<T> | null): ListNode<T> | null {
  let prev: ListNode<T> | null = null
  let current = head
 
  while (current) {
    const next = current.next
    current.next = prev
    prev = current
    current = next
  }
 
  return prev
}

Главная опасность - потерять хвост списка. Поэтому перед current.next = prev мы сохраняем next. Проследим для 1 -> 2 -> 3 -> null:

ШагprevcurrentЧто сделалиСостояние
стартnull1-1 -> 2 -> 3
1121 теперь указывает на nullnull <- 1 2 -> 3
2232 теперь указывает на 1null <- 1 <- 2 3
33null3 теперь указывает на 2null <- 1 <- 2 <- 3

Цикл закончился, prev указывает на новую голову - узел 3. Time O(n), space O(1).

Вставка после известного узла

function insertAfter<T>(node: ListNode<T>, value: T): void {
  node.next = { value, next: node.next }
}

Ничего не сдвигается - меняются только две ссылки, поэтому O(1). В массиве для такой вставки пришлось бы сдвинуть все элементы правее.

Linked list vs array

ОперацияArrayLinked list
access by indexO(1)O(n)
searchO(n)O(n)
insert after known nodeO(n) shiftO(1)
insert at headO(n) (unshift)O(1)
extra memoryменьшессылки на узлы

Что отвечать на собеседовании?

Linked list состоит из узлов, где каждый хранит значение и ссылку на следующий узел. Доступ по индексу медленный, O(n), потому что нужно идти от головы. Зато вставка/удаление после известного узла может быть O(1). На интервью часто спрашивают reverse list, detect cycle, merge two sorted lists.

Что важно помнить: частые ошибки

  • Потерять next при развороте списка.
  • Не обработать head = null.
  • Забыть обновить tail.
  • Путать node и value.
  • Делать рекурсивное решение на очень длинном списке без учета stack.

Мини-шпаргалка

  • Node = value + next.
  • Head - первый узел.
  • Tail - последний узел.
  • Access by index - O(n).
  • Insert after node - O(1).
  • Reverse требует prev/current/next.

Документация

Wikipedia: Linked list, VisuAlgo: Linked List.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам