Linked lists · Связные списки
Nodes joined by links
- A linked list is a chain of nodes.
- Each node holds a piece of data and a link to the next node.
- The last node links to
None, which marks the end.
Узлы, соединенные ссылками
- Связный список — это цепочка узлов.
- Каждый узел содержит часть данных и ссылку на следующий узел.
- Последний узел ссылается на
None, что обозначает конец.
A node is a small record
- We can store one node in a dictionary:
{"data": ..., "next": ...}. "data"holds the value;"next"holds the next node (orNone).- The first node is called the head of the list.
Узел — это маленькая запись
- Мы можем хранить один узел в словаре:
{"data": ..., "next": ...}. "data"хранит значение;"next"хранит следующий узел (илиNone).- Первый узел называется головой списка.
second = {"data": "b", "next": None}
first = {"data": "a", "next": second}
print(first["data"])
print(first["next"]["data"])
Walk the list
- Start at the head and follow each
"next"link. - Stop when you reach
None. - This visiting of every node is called traversal.
Проход по списку
- Начните с головы и следуйте каждой ссылке
"next". - Остановитесь, когда достигнете
None. - Этот обход каждого узла называется проходом (traversal).
head = {"data": 1, "next": {"data": 2, "next": None}}
node = head
while node is not None:
print(node["data"])
node = node["next"]
Why a linked list?
- You can insert or remove a node by changing links — no shifting of items.
- An array would have to move every item after the change.
- But a linked list has no index: to reach item 5 you must walk from the head.
Зачем нужен связный список?
- Вы можете вставить или удалить узел путем изменения ссылок — без сдвига элементов.
- Массиву пришлось бы перемещать каждый элемент после изменения.
- Но у связного списка нет индекса: чтобы добраться до элемента 5, нужно пройти от начала.
In Cambridge pseudocode
- The exam stores nodes in an array;
Nextis the index of the next node, andNULLmarks the end.
В псевдокоде Cambridge
- На экзамене узлы хранятся в массиве;
Next— это индекс следующего узла, аNULLобозначает конец.
TYPE Node
DECLARE Data : INTEGER
DECLARE Next : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].Next
ENDWHILE
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - The last node points to
None.
Распространенные ошибки
- Никогда не теряйте указатель
head, иначе весь список станет недоступным. - Последний узел указывает на
None.
Now you try
- A node is a dict
{"data": ..., "next": ...}. Follow"next"to walk the chain. - Press Check answer to test your code.
Теперь попробуйте сами
- Узел представляет собой словарь
{"data": ..., "next": ...}. Следуйте по ⟨"next"⟩, чтобы пройти по цепочке. - Нажмите Check answer (Проверить ответ), чтобы протестировать свой код.
Nodes linked by pointers · Узлы, связанные указателями
Each node points to the next; you insert/delete by re-linking. · Каждый узел указывает на следующий; вставка/удаление выполняются путём пересвязывания.
Build a linked list 1 → 2 → 3 using dictionaries. Make the three nodes, link each to the next, and point head at the first one. The last node's "next" must be None. · Постройте связный список 1 → 2 → 3, используя словари. Создайте три узла, свяжите каждый со следующим и укажите на первый через переменную head. Значение поля "next" последнего узла должно быть равно None.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Walk the linked list starting at head and add up every node's "data". Store the total in total (the answer is 60). · Пройдите по связному списку, начиная с элемента head, и сложите значения поля "data" каждого узла. Сохраните общую сумму в total (ответ — 60).
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Write length(head) that returns how many nodes are in the linked list. An empty list (head is None) has length 0. · Напишите функцию length(head), которая возвращает количество узлов в связном списке. Пустой список (когда head равно None) имеет длину 0.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.