Обзор

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

На интервью связные списки проверяют не столько знание структур данных, сколько умение аккуратно работать с указателями. Большинство ошибок здесь связано с тем, что кандидат теряет ссылку на следующий узел, неправильно обновляет голову списка или забывает обработать пустой список.

Односвязный список

Один узел односвязного списка обычно выглядит так:

node = {
  val: 10,
  next: nextNode,
};

Список начинается с указателя head. Чтобы добраться до элемента в середине, нужно пройти все предыдущие узлы:

head -> 1 -> 2 -> 3 -> null

Такой обход занимает O(n), но вставка или удаление узла после уже известного узла может выполняться за O(1).

На практике односвязный список часто используют для FIFO-очереди. Новый элемент добавляют в конец, а забирают с начала. Если хранить и head, и tail, обе операции выполняются за O(1). Именно поэтому очередь на связном списке удобнее простой очереди на массиве: при удалении с начала не нужно сдвигать все остальные элементы.

Двусвязный список

В двусвязном списке у каждого узла есть две ссылки: на следующий и на предыдущий узел.

node = {
  val: 10,
  next: nextNode,
  prev: previousNode,
};

Список можно представить так:

null <-> 1 <-> 2 <-> 3 <-> null

Голова списка по-прежнему хранится в head. Иногда отдельно хранят и tail - последний узел. Тогда добавление в конец списка можно делать за O(1).

Главное отличие от односвязного списка: мы можем идти не только вперед, но и назад. Это упрощает удаление текущего узла, если у нас уже есть указатель на него. Для внутреннего узла достаточно связать prev и next соседей, не проходя список с начала.

node.prev.next = node.next;
node.next.prev = node.prev;

На интервью двусвязные списки встречаются реже односвязных, но идея та же: нужно следить за всеми ссылками, которые меняются. Здесь их на одну больше, и ошибка в prev или next может сломать обход в обе стороны.

Типичный пример применения - LRU-кэш. Мы храним элементы в двусвязном списке по порядку использования: недавние - ближе к голове, давно не использованные - ближе к хвосту. Хеш-таблица хранит ключ и указатель на узел списка. Когда элемент снова нужен, мы быстро находим его узел и переставляем в начало. Когда кэш переполняется, удаляем последний узел. Без prev такое удаление и перестановка были бы заметно сложнее.

Когда использовать

Задачи на связные списки обычно требуют:

1. Развернуть список полностью или частично.

2. Найти середину списка.

3. Обнаружить цикл.

4. Слить два отсортированных списка.

5. Удалить или переставить узлы без создания нового списка.

В таких задачах важно думать не о значениях, а о связях между узлами. Мы меняем не массив, а стрелки next или prev.

Рабочий прием

Перед изменением ссылки next почти всегда нужно сохранить следующий узел во временную переменную.

next = current.next;
current.next = previous;
previous = current;
current = next;

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

Итоги

Связные списки требуют внимательности к порядку операций. Хорошее решение обычно состоит из небольшого числа указателей и четкого инварианта: какая часть списка уже обработана, а какая еще нет.