Связанный список (linked list) – это структура данных, представляющая собой линейную последовательность элементов, каждый из которых содержит данные и ссылку на следующий элемент списка. В отличие от массивов или встроенных типов данных Python, таких как списки (list) или кортежи (tuple), элементы связанного списка не располагаются последовательно в памяти компьютера; вместо этого они связаны друг с другом через указатели.
Типы связанных списков
Существует несколько видов связанных списков:
1️⃣Односвязные (singly linked lists): Каждый узел хранит ссылку только на следующий узел.
2️⃣Двусвязные (doubly linked lists): Узлы содержат ссылки как на предыдущий, так и на следующий узлы.
3️⃣Кольцевые (circular linked lists): Последний узел указывает на первый, образуя кольцо.
Преимущества и недостатки
Преимущества использования связанных списков включают:
1️⃣ Эффективное добавление/удаление элементов в произвольных позициях за время O(1).
2️⃣ Возможность работы с неограниченным количеством элементов без необходимости выделения большого объема непрерывного пространства памяти заранее.
3️⃣ Простота реализации динамических структур данных.
Недостатки:
1️⃣ Доступ к произвольному элементу требует времени O(n), где n - количество узлов до искомого элемента.
2️⃣ Дополнительная память расходуется на хранение ссылок между узлами.
Реализация односвязного списка на Python
Для наглядности хорошо продемонстрирована в телеграмм канале.
Подпишись на нас - будет много разборов интересного.
В телеграмм - https://t.me/john_soi_blog
В дзене - https://dzen.ru/john_soi_blog
Boosty - https://boosty.to/dh_education/donate
VK - https://vk.com/dh_edu