Связные списки
Узлы, соединенные ссылками
- Связный список — это цепочка узлов.
- Каждый узел содержит часть данных и ссылку на следующий узел.
- Последний узел ссылается на
None, что обозначает конец.
Узел — это маленькая запись
- Мы можем хранить один узел в словаре:
{"data": ..., "next": ...}. "data"хранит значение;"next"хранит следующий узел (илиNone).- Первый узел называется головой списка.
second = {"data": "b", "next": None}
first = {"data": "a", "next": second}
print(first["data"])
print(first["next"]["data"])
Проход по списку
- Начните с головы и следуйте каждой ссылке
"next". - Остановитесь, когда достигнете
None. - Этот обход каждого узла называется проходом (traversal).
head = {"data": 1, "next": {"data": 2, "next": None}}
node = head
while node is not None:
print(node["data"])
node = node["next"]
Зачем нужен связный список?
- Вы можете вставить или удалить узел путем изменения ссылок — без сдвига элементов.
- Массиву пришлось бы перемещать каждый элемент после изменения.
- Но у связного списка нет индекса: чтобы добраться до элемента 5, нужно пройти от начала.
В псевдокоде Cambridge
- На экзамене узлы хранятся в массиве;
NextIndex— это индекс следующего узла, аNULLобозначает конец.
TYPE Node
DECLARE Data : INTEGER
DECLARE NextIndex : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].NextIndex
ENDWHILE
Распространенные ошибки
- Никогда не теряйте указатель
head, иначе весь список станет недоступным. - Последний узел указывает на
None.
Теперь попробуйте сами
- Узел представляет собой словарь
{"data": ..., "next": ...}. Следуйте"next"для обхода цепочки. - Нажмите Check answer (Проверить ответ), чтобы протестировать свой код.
Узлы, связанные указателями
Каждый узел указывает на следующий; вставка/удаление выполняются путём пересвязывания.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Постройте связный список 1 → 2 → 3, используя словари. Создайте три узла, свяжите каждый со следующим и укажите на первый через переменную head. Значение поля "next" последнего узла должно быть равно None.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Пройдите по связному списку, начиная с элемента head, и сложите значения поля "data" каждого узла. Сохраните общую сумму в total (ответ — 60).
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Напишите функцию length(head), которая возвращает количество узлов в связном списке. Пустой список (когда head равно None) имеет длину 0.
Нажмите Запустить, чтобы увидеть результат здесь.