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

Чтобы добавить значение в начало связного списка, меняются два указателя, будь в списке 4 значения или 4 миллиона.

Значения, которые указывают на следующее

Массив держит значения рядом друг с другом, поэтому начало дорого менять. Связный список отказывается от этого правила. Каждое значение живёт в своей маленькой записи, она называется узлом, и узлы могут лежать где угодно в памяти. В конспектах MIT 6.006 узел описан двумя полями: item (элемент) и next, указатель на следующий узел. Сам список помнит только первый узел, он называется головой (head). У последнего узла next равно null, это отмечает конец.

Чтобы прочитать список, начинают с head и идут по указателям next по одному, как по цепочке записок, где в каждой сказано, где спрятана следующая. У этого есть цена. Формулы для адреса четвёртого узла нет, поэтому получить значение на позиции i значит посетить i + 1 узлов. В списке MIT операция get at(i) для связного списка указана как O(n), а массив справлялся с ней за один шаг.

// один узел на значение: { value, next }
let head = null;
for (const v of [4, 30, 7, 12]) head = { value: v, next: head };
// проход по списку
for (let n = head; n !== null; n = n.next) console.log(n.value); // 12, 7, 30, 4

Изменение списка перестановкой ссылок

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

В середине работа состоит в том, чтобы найти место. Чтобы вставить на позицию i, дойди до узла прямо перед ней (i посещений), затем сделай те же два изменения указателей: new.next = prev.next, затем prev.next = new. Порядок важен. Если сначала задать prev.next, остаток списка потеряется, потому что на него больше ничего не указывает. В лаборатории шагом считается одно посещение узла или одно изменение указателя, так что вставка на позицию 2 в список из 4 узлов стоит 2 посещения плюс 2 изменения, 4 шага.

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

Связный список хорошо подходит, когда большинство изменений происходит там, куда у тебя уже есть указатель, например в начале, а позиция i нужна редко. Из связных списков можно строить очереди и стеки, а также цепочки внутри хеш-таблицы из следующего урока. Есть варианты. Двусвязный список даёт каждому узлу ещё и указатель prev, так что можно идти назад и удалять узел за один шаг, когда он уже найден. Если хранить, кроме head, ещё и указатель tail, добавление в конец становится дешёвым.

В повседневном JavaScript связный список пишут редко, потому что массивы хорошо оптимизированы, а кэши современных процессоров любят значения, лежащие рядом. Но идея всё равно важна: деревья, графы и многие библиотечные структуры построены из узлов и указателей именно так.