Связный список: ссылка вместо адреса

Если ты знаешь, что такое узел и ссылка, почему индексация связного списка - O(n), а вставка «на месте» - O(1), и чем односвязный отличается от двусвязного, листай до «Теперь сам».

Как думаешь, как хранить последовательность, не держа её подряд

У массива всё хорошо с доступом, но плохо с правками в середине - и виной непрерывная укладка: элементы лежат вплотную, поэтому любую дырку надо закрывать сдвигом. А что, если РАЗРЕШИТЬ элементам лежать не подряд, вразброс по памяти? Тогда сдвигать будет нечего - но появится новая задача: как понять, какой элемент за каким идёт, если по адресу это больше не прочитать. Ответ и даёт связный список: пусть каждый элемент сам хранит, где лежит следующий.

На что это похоже

Квест-игра: на первой записке написан адрес, где спрятана вторая записка, на второй - где третья, и так далее. Записки могут лежать в разных концах города - порядок задают не их места, а ссылки «дальше туда-то». Чтобы добраться до пятой записки, ты обязан пройти первые четыре: перескочить нельзя, адрес пятой знает только четвёртая. Но ВКЛЕИТЬ новую записку между третьей и четвёртой легко: перепишешь ссылку на третьей, чтобы она вела на новую, а новую - на четвёртую. Никого не пришлось перекладывать.

Механизм: узел, ссылка, проход

Элемент связного списка - это узел: пара «значение + ссылка на следующий узел». У последнего узла ссылка пустая (конец цепочки). Отдельно хранится ссылка на первый узел - голову, а обычно ещё и на последний - хвост. Хвост нужен, чтобы добавлять в конец за O(1): без ссылки на последний узел до него пришлось бы идти через всю цепочку (O(n)), а с ней - сразу перецепить. Узлы лежат в памяти где попало; последовательность держат только ссылки.

Индексация - O(n). Прямого адреса i-го узла нет: чтобы до него добраться, берёшь голову и i раз идёшь по ссылке «следующий». До серединного элемента - n/2 шагов, до последнего - n. Никакой арифметики, только проход.

Вставка и удаление на месте - O(1). Если ты УЖЕ стоишь у узла, после которого надо вставить x: создаёшь узел x, его ссылку направляешь туда, куда указывал текущий, а ссылку текущего - на x. Две перецепки, ничего не сдвигается - O(1). Удаление так же: ссылку предыдущего перекинуть через удаляемый на следующий за ним.

Правило

Связный список хранит элементы узлами «значение + ссылка на следующий», вразброс по памяти. Индексация и поиск - O(n) (проход по ссылкам от головы), зато вставка и удаление НА МЕСТЕ (когда ты уже у нужного узла) - O(1) (перецепить ссылки, без сдвига). Профиль обратный массиву. В двусвязном списке узел ссылается и на предыдущего - дёшев и шаг назад, ценой лишней ссылки в каждом узле.

Разбор: почему вставка «на месте» - это O(1), а не O(n)

Сравни с массивом. В массиве вставка в середину дорога, потому что элементы лежат вплотную и хвост надо сдвинуть. В связном списке двигать нечего: узлы и так разбросаны, их порядок - это ссылки. Стоишь у узла b и хочешь вставить x после него: заводишь узел x, ссылку x → (то, на что смотрел b), потом b → x. Всё, x в цепочке между b и бывшим следующим. Две операции со ссылками, от длины списка не зависит - O(1). Оговорка важна: это O(1), если ты УЖЕ стоишь у места вставки. Если места ещё надо ДОСТИЧЬ по индексу - плюс O(n) на проход. Дёшева именно перецепка, а не поиск места.

Разбор: односвязный и двусвязный

В односвязном списке узел знает только следующего. Идти можно лишь вперёд, и чтобы удалить узел, нужна ссылка на ПРЕДЫДУЩИЙ (это его ссылку перекидывают) - а до неё из самого узла не добраться. Двусвязный список чинит это: каждый узел хранит две ссылки, на следующего и на предыдущего. Тогда дёшев шаг в обе стороны, а удаление узла, на который ты смотришь, - O(1) (предыдущий и следующий известны сразу). Плата - лишняя ссылка в каждом узле: больше памяти и на одну перецепку больше при вставке. На двусвязном списке, кстати, удобно строить деку - структуру со вставкой и снятием с обоих концов, но об этом в следующей главе.

Что ломается без этого

Главная ошибка - обращаться к связному списку по индексу в цикле, как к массиву: for i in range(n): ... list[i] на связном списке даёт O(n²), потому что каждый list[i] - это проход i шагов от головы. По связному списку ходят ОДНИМ проходом подряд (от узла к узлу), а не индексом. Вторая ошибка - ждать от связного списка быстрого доступа к серединному элементу: его нет и быть не может, прямого адреса у узла нет. И третья - забыть, что дешёвая вставка O(1) - это про случай «я уже у места»; если до места надо дойти поиском, добавь стоимость прохода.

Зачем это в работе

Связные списки лежат в основе структур, где важны частые вставки и удаления не с края: очереди и деки (двусвязный список даёт O(1) на обоих концах - так устроен deque в Python), списки задач, из которых часто выдёргивают элементы из середины по уже имеющейся ссылке. Но у связного списка есть скрытая цена, которой нет в таблице порядков роста: узлы разбросаны по памяти, и процессор не может подгружать их пачками, как непрерывный массив. Из-за этого на практике массив (с его O(1)-доступом и плотной укладкой) часто обгоняет связный список даже там, где по «бумажной» асимптотике список выглядит выигрышнее. Когда что выбирать - разбор в следующем уроке.

Теперь сам

По связному списку из n узлов ты n раз выполняешь «вставить новый элемент СРАЗУ ПОСЛЕ головы» (голова известна всегда). Во что обойдётся вся серия? А если бы это был массив и ты n раз делал insert(1, x)?