Связные списки

Перед началом: стек, очередь и дек (модуль 5). Инструменты: Go 1.27, container/list. Трудоёмкость: ~4 ч (теория 1.5 ч · практика 2.5 ч).

🔥 Инцидент: «Кэш не вытеснял — память росла три недели»

В шлюзе появился маленький кэш «последних 10 000 ответов». Реализация была на одной map: ключ → значение. Кэш исправно отдавал попадания… и не вытеснял ничего. Через три недели процесс занимал 14 ГБ, и его пришлось перезапускать по расписанию, потому что «так надёжнее». Причина простая: в map нет порядка использования, а значит, некому ответить на вопрос «какая запись самая старая?».

Нужная структура — комбинация двух: map для мгновенного доступа и связный список для порядка. В модуле — связные списки: разворот, поиск середины, детект цикла и LRU-кэш, который на этом строится. И честный разговор о том, почему в Go-коде вы чаще увидите срез, чем список.

📖 Теория

6.1 Зачем список, если есть срез

Связный список даёт O(1) на вставку и удаление при известном узле: переставить указатели дешевле, чем сдвигать хвост среза. Плата:

Практический вывод для Go: срез выигрывает почти везде, где нужен доступ по индексу или обход. Список незаменим там, где узел уже под рукой и нужны перестановки: LRU-кэш, планировщики, буферы фиксированной ёмкости.

6.2 Разворот односвязного списка

Классика собеседований, и не зря: в трёх строках нужно не потерять хвост.

go
type listNode struct {
	val  int
	next *listNode
}

// reverse — итеративно: prev идёт за cur, next держит остаток.
func reverse(head *listNode) *listNode {
	var prev *listNode
	for cur := head; cur != nil; {
		next := cur.next // 1) запомнить остаток
		cur.next = prev  // 2) развернуть текущий указатель
		prev = cur       // 3) подвинуть prev
		cur = next       // 4) подвинуть cur
	}
	return prev // новая голова
}

Рекурсивный вариант короче, но платит глубиной стека (модуль 11) и неочевидным возвратом значения — итеративная версия в продакшене предпочтительнее.

6.3 Fast/slow: середина и цикл

Два указателя с разной скоростью решают сразу два вопроса без подсчёта длины:

go
// middle — середина списка: fast идёт вдвое быстрее.
func middle(head *listNode) *listNode {
	slow, fast := head, head
	for fast != nil && fast.next != nil {
		slow = slow.next
		fast = fast.next.next
	}
	return slow // для чётной длины — правая из двух середин
}

// hasCycle — цикл по Флойду: быстрый догонит медленного внутри цикла.
func hasCycle(head *listNode) bool {
	slow, fast := head, head
	for fast != nil && fast.next != nil {
		slow, fast = slow.next, fast.next.next
		if slow == fast {
			return true
		}
	}
	return false
}

Точка входа в цикл ищется красивым продолжением: после встречи один указатель возвращают к голове и двигают оба по шагу — они встретятся именно на входе в цикл (доказательство — арифметика расстояний, полезно уметь объяснить).

6.4 Двусвязный список со sentinel и LRU-кэш

Двусвязный список добавляет prev, а приём sentinel (узел-часовой без данных) убирает все проверки на nil: голова и хвост — соседи sentinel, у каждого узла гарантированно есть оба соседа.

LRU-кэш собирается из двух структур: map ключ → узел даёт O(1) доступ, список хранит порядок использования. Свежий элемент — в голове; при переполнении выбрасывается хвост; чтение передвигает узел в голову.

go
type lru struct {
	cap   int
	items map[int]*lruNode // ключ -> узел списка
	head  *lruNode         // самые свежие
	tail  *lruNode         // кандидаты на вытеснение
}

// get: нашлось — поднять в голову и вернуть true.
// put: есть — обновить и поднять; нет — создать в голове,
//      при переполнении удалить хвост и его ключ из map.

Именно этого не хватало инциденту: map отвечала «есть или нет», а порядок держит список.

6.5 container/list: когда стандартная библиотека уместна

В Go есть готовый двусвязный список — container/list с Element (значение any). Он честно решает задачу, но:

• элементы хранятся как any — аллокации на упаковку значений;
• API требует приведения типов, читаемость страдает;
• для большинства задач срез всё равно быстрее из-за кэша.

Разумный ориентир: свой узел со конкретным типом вместо any, если список — горячий путь; container/list — если нужен одноразовый рабочий инструмент и важна готовность; срез — по умолчанию.

6.6 Компромиссы

💻 Практика

1. Базовый набор. Реализуйте односвязный список с Push (в голову), Reverse, Middle (fast/slow) и HasCycle. Тесты: пустой список, один элемент, чётная и нечётная длина, цикл на первом/последнем узле.
2. Merge two sorted. Слияние двух отсортированных списков за O(n+m), собирая новый список из существующих узлов (без аллокаций новых).
3. Точка входа в цикл. Продолжите §6.3: после встречи верните указатель к голове и найдите узел, с которого начинается цикл. Проверьте тестом: цикл начинается в середине, в голове, у последнего узла.
4. LRU-кэш. Реализуйте Get/Put с ёмкостью 2 и прогоните сценарий: Put(1), Put(2), Get(1), Put(3) (вытесняет 2), Get(2) → нет, Get(1) → есть. Именно этот сценарий ловит ошибки порядка.
5. Срез против списка. Сравните на 100 000 элементов: вставка в начало срезом (slices.Insert со сдвигом) против списка (O(1)), и обход обеих структур. Замерьте операции счётчиками (сдвинутые элементы против шагов по указателям) и объясните, где срез всё равно выиграет.

🧩 Quiz

✅ Итоги модуля

• Список — это O(1) на перестановки при известном узле; плата — указатели и кэш-промахи; срез в Go выигрывает почти везде, кроме «порядка под рукой».
• Разворот — три указателя в правильном порядке; fast/slow находят середину и цикл (Флойд), точка входа — вторым этапом.
• Sentinel убирает nil-ветки; LRU-кэш — канонический союз map (доступ) и списка (порядок).
• container/list уместен как готовый инструмент, но типизированный свой узел предпочтительнее в горячем пути.

🔗 Мостик к Модулю 7

Структуры хранения закончились — начинается «поиск решений». Бэктрекинг иерархически пробует варианты и откатывается, как обход дерева: choose — explore — unchoose. В модуле 7 — «Рекурсия и перебор с возвратом»: подмножества и перестановки, комбинации с суммой, отсечения и N-ферзей — и разговор о том, когда перебор ускоряется отсечениями, а когда его нужно менять на DP.