Алгоритмы с нуля
Связный список
Ты знаешь, что массив — это ряд смежных ячеек в памяти, и что смежность даёт тебе O(1) индексирование, но O(n) вставку в середину. Теперь представь другую структуру: узлы разбросаны по памяти, каждый держит значение и указывает на следующий узел. Это связный список. Ты теряешь суперсилу O(1) индексирования — нахождение 5-го элемента теперь стоит O(n) — но получаешь суперсилу: вставка в начало за O(1), без сдвигов.
После этого урока ты можешь объяснить, что такое узел и указатель, нарисовать связный список в памяти, реализовать push (вставку в начало) и обход, понять, почему индексирование по позиции O(n), а вставка в начало O(1), сравнить временные и пространственные затраты операций связного списка и массива, и узнать, когда связный список — правильный выбор.
Базовая идея: узлы и указатели
Массив — это ряд ячеек, выстроенных в ряд. Связный список — это последовательность узлов. Каждый узел — маленький контейнер, держащий две вещи:
- Значение (данные, что ты хочешь хранить)
- Указатель (адрес памяти, указывающий на следующий узел)
Связный список начинается со специального узла, называемого head (голова). Если ты хочешь посетить каждое значение, начни с head, прочитай значение, проследуй по указателю на следующий узел, и повтори.
Пример: связный список, содержащий [10, 20, 30]:
head → [10 | next → ] → [20 | next → ] → [30 | next → null]Каждый [ value | next → ] это узел. Указатель следующего узла это null, означая «больше нет узлов».
Почему разреженная память важна:
Массивы хранят все элементы в смежном блоке. Компьютер может вычислить адрес любого элемента мгновенно: base_address + (index × element_size).
Связные списки иные. Узлы могут храниться где угодно в памяти. Чтобы найти узел на позиции 5, ты не можешь вычислить его адрес. Вместо этого ты должен начать с head, проследить указатель, шаг 1, шаг 2, шаг 3, шаг 4, шаг 5. Это стоит O(n) времени.
Почему указатели важны:
Потому что узлы разреженны, каждый узел должен хранить адрес следующего узла. Тот адрес — это указатель. В памяти указатель это просто число — обычно 8 байт на 64-битной системе — но оно говорит компьютеру: «Следующий кусок данных находится по этому адресу».
Пример расположения в памяти (воображаемый):
Адрес 1000: узел 1 = [10, указатель на 3008]
Адрес 3008: узел 2 = [20, указатель на 5016]
Адрес 5016: узел 3 = [30, указатель на null]Заметь, что адреса не последовательны. Узлы 1, 2, 3 лежат на 1000, 3008, 5016. Но каждый узел указывает на следующий, так что мы можем обойти список.
Вставка в начало: суперсила связного списка
В массиве вставка в начало требует сдвига всех n элементов. Дорого.
В связном списке вставка в начало тривиальна:
- Создай новый узел со своим значением.
- Установи его указатель на текущий head.
- Обнови head, чтобы он указывал на новый узел.
Это три операции. Время: O(1).
1
class Node {
2
constructor(value, next = null) {
3
this.value = value;
4
this.next = next;
5
}
6
}
7
8
let head = new Node(10); // Список: [10]
9
10
// Вставь 20 в начало
11
head = new Node(20, head); // Список: [20, 10]
12
13
// Вставь 30 в начало
14
head = new Node(30, head); // Список: [30, 20, 10]
- L1 Каждый узел держит значение и указатель на следующий узел
- L8 Создай первый узел
- L11 Создай новый узел, указывающий на старый head
- L14 Обнови head на новый узел. O(1) — без сдвигов!
Обход: стоимость связного списка
Чтобы найти значение или получить доступ на позицию i, ты должен обойти с head:
1
function getAtIndex(head, index) {
2
let current = head;
3
for (let i = 0; i < index; i++) {
4
if (current === null) return null; // Конец списка
5
current = current.next; // Проследуй указатель
6
}
7
return current?.value;
8
}
- L2 Начни с head
- L3 Цикл index раз
- L5 Проследуй указатель на следующий узел
- L8 Верни значение на позиции index, или null если не найдено
Для списка из n узлов поиск позиции i стоит O(i) времени. В худшем случае (i = n) это O(n).
Связный список в сравнении с массивом в целом:
| Операция | Массив | Связный список |
|---|---|---|
| Доступ по индексу | O(1) | O(n) |
| Вставка в начало | O(n) | O(1) |
| Вставка в середину | O(n) | O(n) |
| Вставка в конец | O(1) амортизировано | O(n) |
| Удаление в начале | O(n) | O(1) |
| Удаление в середине | O(n) | O(n) |
| Поиск значения | O(n) | O(n) |
Трейд-офф: массивы быстры для чтения; связные списки быстры для вставки в начало.
Давай построим простой класс связного списка с push (вставка в начало) и обходом:
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
}
// Вставка в начало: O(1)
push(value) {
this.head = new Node(value, this.head);
}
// Получить значение на индексе: O(n)
getAtIndex(index) {
let current = this.head;
for (let i = 0; i < index; i++) {
if (current === null) return null;
current = current.next;
}
return current?.value;
}
// Получить узел на индексе (полезно для удаления/вставки): O(n)
getNodeAt(index) {
let current = this.head;
for (let i = 0; i < index; i++) {
if (current === null) return null;
current = current.next;
}
return current;
}
// Обход и печать всех значений: O(n)
traverse() {
const values = [];
let current = this.head;
while (current !== null) {
values.push(current.value);
current = current.next;
}
return values;
}
}Попробуй построить и обойти связный список:
Давай проследим операцию push пошагово. Начинаем с пустого списка и вставляем три значения: 10, 20, 30.
1
const list = new LinkedList();
2
list.push(10);
3
list.push(20);
4
list.push(30);
Теперь проследим вызов getAtIndex(2) на списке [30, 20, 10]:
1
function getAtIndex(index) {
2
let current = head;
3
for (let i = 0; i < index; i++) {
4
current = current.next;
5
}
6
return current?.value;
7
}
Каждый прыжок на следующий узел это один шаг. Чтобы достичь позицию i, ты должен прыгнуть i раз. Время: O(i).
Операции связного списка:
| Операция | Время | Пространство |
|---|---|---|
| Доступ к элементу на индексе i | O(i) | O(1) aux |
| Поиск значения | O(n) | O(1) aux |
| Push (вставка в начало) | O(1) | O(1) |
| Вставка после узла на индексе i | O(i) чтобы найти узел, потом O(1) вставить | O(1) |
| Удаление в начале | O(1) | O(1) |
| Удаление на индексе i | O(i) | O(1) |
| Обход всех | O(n) | O(1) aux |
Почему push это O(1)? Ты создаёшь новый узел и обновляешь один указатель. Две операции. Без обхода.
Почему доступ по индексу O(n)? Ты должен проследить указатели один за другим. Нет формулы, чтобы прыгнуть сразу на позицию i.
Контраст с массивами:
Массивы O(1) для индексирования, потому что память смежна. Связные списки O(n), потому что память разреженна и ты должен проследить указатели.
Интуиция: Смежность даёт расчёт. Разреженность требует обхода.
В связном списке из 1000 узлов сколько времени требуется, чтобы найти узел на индексе 500?
В связном списке почему вставка в начало O(1)?
Массив из 100 элементов даёт O(1) доступ к arr[99]. Связный список из 100 узлов требует O(n) чтобы дошла до узла 99. Почему эта разница?
Ты вставляешь значения 10, 20, 30 в начало связного списка (в таком порядке). Какой список после всех трёх pushes?
В связном списке почему ты не можешь просто вычислить адрес памяти узла на позиции i, как ты делаешь в массиве?
Граничные случаи
Вставка в середину: Если у тебя есть ссылка на узел и ты хочешь вставить после него, это O(1) — просто перенаправь указатель. Но если ты хочешь вставить на позицию i (где у тебя ещё нет ссылки), ты должен сначала обойти на позицию i, что стоит O(i). Итак, «вставка на позицию i» в связном списке это O(i), не O(1).
Частая ошибка
«Связные списки всегда медленнее.» Неправда. Связные списки медленнее на индексирование (O(n)), но быстрее на вставку в начало (O(1)). Правильный инструмент зависит от задачи. Если ты часто вставляешь в начало и редко индексируешь, связный список лучше. Если ты часто индексируешь, массив лучше.
Почему связный список достигает O(1) вставки в начало, пока массив требует O(n) для вставки в начало?
Связный список — это последовательность узлов, каждый держит значение и указатель на следующий узел.
Ключевые факты:
- Узел: Контейнер с двумя полями — значение и next (указатель на следующий узел).
- Head: Первый узел. Обход начинается отсюда.
- Указатель: Адрес памяти, указывающий на следующий узел.
- Разреженная память: Узлы не смежны. Указатели связывают их вместе.
- Индексирование это O(n): Нет формулы для прыжка на позицию i. Должен проследить указатели один за другим.
- Push это O(1): Создай новый узел, укажи его на старый head, обнови head. Без сдвигов.
- Трейд-офф: Теряешь O(1) индексирование; получаешь O(1) вставку в начало.
- Используй когда: Частые вставки в начало, редкий случайный доступ.
Далее ты изучишь стек и очередь — две другие последовательные структуры данных, построенные на связных списках, каждая со своей дисциплиной и вариантами использования.