Урок 10: Связные списки
Представьте поиск сокровищ: каждая записка хранит значение и подсказку к следующей записке, и чтобы добраться до пятой, нужно идти по одной за раз. Это «связный список» (linked list) — цепочка «узлов» (nodes). Плюс: вставка или удаление в середине выполняется за O(1) — нужно лишь перенаправить подск
Связный список похож на поиск сокровищ: каждая записка хранит значение и подсказку, куда идти дальше. Чтобы добраться до пятой записки, нужно следовать подсказкам одну за другой — нельзя перепрыгнуть сразу в середину, как в массиве, где можно обратиться к любому месту мгновенно.
- класс (class)
- Шаблон для небольшой коробки с полями. class Node определяет коробку с двумя полями: val (значение) и next (указатель на следующий узел). Node(1) создаёт такую коробку, а self означает просто «эту коробку».
- связный список
- Структура данных из узлов, каждый из которых хранит значение и указатель next на следующий узел; вставка/удаление рядом с известным узлом за O(1), но доступ по позиции за O(n).
- узел (node)
- Строительный блок связного списка: небольшой объект, хранящий значение (val) и указатель (next) на следующий узел, либо None в конце.
- локальность кэша (cache locality)
- Насколько близко в памяти хранятся данные, используемые вместе; непрерывный массив дружелюбен к кэшу, тогда как разбросанные узлы связного списка — в меньшей степени.
