TwiddleLab / Код / Структуры данных, которые видно
Связные списки: цепочки стрелок
Что ты узнаешь
- Если поставить элемент в начало списка Python, сдвигается каждый другой элемент: n перемещений для n элементов.
- Связный список это цепочка узлов. Каждый узел хранит значение и стрелку на следующий узел; последний указывает на None.
- Вставка или удаление это перестановка одной-двух стрелок, какой бы длинной ни была цепочка. Переставляй их в правильном порядке, иначе часть цепочки потеряется.
- Цена: чтобы добраться до элемента 5000, нужно пройти по 5000 стрелкам. Список прыгает туда за один шаг.
Как идёт урок
Добавляешь одну песню в начало плейлиста из 10 000 песен.
Телефон правда двигает 10 000 песен? Сделай догадку.
В ряду шкафчиков начало это шкафчик 0.
Вставь туда новую песню и посчитай каждое перемещение.
Шкафчики стоят рядом, пронумерованы с 0. Чтобы освободить шкафчик 0, песня из него должна уйти в 1, из 1 в 2 и так до конца.
Другой способ: песни, соединённые стрелками.
Выбери песню, потом переставь стрелки, чтобы плейлист начинался с неё.
Каждая песня знает только, где следующая. Чтобы поставить песню первой, она должна указывать на прежнюю первую, а head должен указывать на неё. Больше ничего не меняется.
Эта цепочка это связный список.
Связный список это цепочка узлов. Каждый узел хранит значение и стрелку, которая называется next, на следующий узел.
head указывает на первый узел. next последнего узла это None: конец цепочки.
Без классов узел может быть словарём: {"val": "Ava", "next": None}. Стрелка это просто ссылка на другой словарь.
Поставь Echo сразу после Bo.
Снова две стрелки. На этот раз важен порядок, в котором их переставлять.
Если Bo сначала отпустит Cleo, на Cleo больше ничто не указывает, и программе никак снова не найти Cleo и Dax. Поэтому Echo должна указать на Cleo раньше, чем Bo укажет на Echo.
Как программа проигрывает цепочку.
Пройди по шагам. Каждый раз, когда node двигается, нажми на песню, куда он попал.
Гонка перестановок.
Четыре задания на цепочке. Переставляй стрелки как можно меньше раз.
Значит, цепочка всегда лучше?
Два задания на плейлисте из 10 000 песен. Для каждого нажми на более быструю структуру, потом «Проверить».
В списке элемент i лежит в известном месте, поэтому прыжок туда это один шаг, а сдвиг это n перемещений. В связном списке нет номера, чтобы прыгнуть, есть только стрелки, по которым идти, зато для вставки достаточно поменять две стрелки.
Два сломанных плейлиста. Почини их.
В каждом одна неверная стрелка. Найди её и направь куда нужно.
Предыдущий урок: Очередь: первым пришёл, первым ушёл · Следующий урок: Хеш-таблицы: как словари находят · Часть курса: Структуры данных, которые видно
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
