Связный список — одна из фундаментальных структур данных в программировании. Он состоит из набора элементов, называемых узлами. Каждый узел содержит данные и ссылку на следующий узел в последовательности. По своей природе связные списки обладают уникальной динамичностью и гибкостью, что позволяет эффективно управлять элементами в памяти.
Узлы и Связи: основные элементы связного списка
Как было отмечено ранее, основными составляющими связного списка являются узлы и связи. Узел состоит из двух частей: собственно данных и ссылки на следующий узел. В случае односвязного списка каждая связь указывает только на следующий элемент, что облегчает проход от начала к концу, но не позволяет вернуться назад.
Поскольку в односвязном списке мы можем двигаться только вперёд, важнейшим элементом является указатель на первый узел, который называется головным. Именно от него начинается работа со связным списком, и через него можно последовательно обойти все элементы структуры.
Связный список — это структура данных, которая состоит из элементов, зовущихся узлами. В узлах хранятся данные, а между собой узлы соединены связями.
Связь — это ссылка на следующий или предыдущий элемент списка.
В результате у нас образуется два класса: узел и список.
В узлах хранятся данные, а это значит, что первый атрибут класса узел у нас приобретает значение.
Между собой узлы соединены связями, в односвязном списке связь — это ссылка на следующий элемент списка.
Таким образом, узел состоит из значения и одной связи на следующий узел.
Список состоит из нескольких узлов, последовательное подключение которых образует головной элемент за которым идёт хвост, состоящий из добавленных узлов.
При программировании в связных списках нам необходим указатель, который позволит идти по этим узлам.
В односвязном списке мы продвигаемся только в сторону конца списка, поэтому изначально атрибут у нас будет в единственном экземпляре, в виде указателя на самый первый элемент, то есть головной узел списка.
Реализация Односвязного Списка в Python
Теперь давайте реализуем простой односвязный список на Python и разберём код по частям.
Тот же код ниже для копирования и вставки в программу. Не забывайте про необходимый отступ пробелами в определённых местах в начале строки, так как код на сервере блога может отображаться некорректно.
class Node:
def __init__(self, data):
self.data = data # Здесь хранятся данные узла
self.next = None # Изначально ссылка на следующий узел отсутствует, т.е. указывает на None
class LinkedList:
def __init__(self):
self.head = None # Начало списка. Сначала список пустой, поэтому голова указывает на None
def append(self, data):
new_node = Node(data) # Создаём новый узел с указанными данными
if not self.head:
self.head = new_node # Если список пустой, новый узел становится головой списка
return
last = self.head
while last.next:
last = last.next # Идём до последнего узла
last.next = new_node # Добавляем новый узел в конец списка
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next # Переход к следующему узлу
print("None") # Указываем на конец списка
# Использование связного списка
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.display()
Расшифровка кода
- Класс Node: def __init__(self, data): конструктор принимает параметр data, который хранит данные узла.
self.data: атрибут для хранения данных узла.
self.next: ссылка на следующий узел, изначально равна None. - Класс LinkedList: def __init__(self): инициализирует новый пустой список с головой, указывающей на None.
- def append(self, data): добавляет новый узел с данными data в конец списка. Проверяет, пуст ли список, если да, назначает новый узел головой.
В противном случае, ищет последний узел и добавляет новый узел в его конец. - def display(self): отображает список, проходя от головы до конца и выводя данные каждого узла.
Результат работы кода:
Рекомендации по усовершенствованию кода
- Метод для удаления узлов: Реализуйте метод для удаления узла по значению, что значительно расширит функциональность.
- Поиск и возврат узла: Добавьте возможность поиска узлов по значению.
- Обработка исключений: Обработайте ситуации, когда удаляемый элемент отсутствует, чтобы избежать ошибок.
Заключение
Связные списки — мощная и гибкая структура данных, которая предоставляет простоту динамических операций с элементами. Односвязные списки идеально подходят для приложений, требующих последовательного доступа с минимальными операциями по вставке и удалению, например, для очередей или стэков. Надеюсь, эта статья помогла вам лучше понять и реализовать односвязный список на Python.
Полезные ресурсы:
---------------------------------------------------
Сообщество дизайнеров в VK
https://vk.com/grafantonkozlov
Телеграмм канал сообщества
https://t.me/grafantonkozlov
Архив эксклюзивного контента
https://boosty.to/antonkzv
Канал на Дзен
https://dzen.ru/grafantonkozlov
---------------------------------------------------
Бесплатный Хостинг и доменное имя
https://tilda.cc/?r=4159746
Мощная и надежная нейронная сеть Gerwin AI
https://t.me/GerwinPromoBot?start=referrer_3CKSERJX
GPTs — плагины и ассистенты для ChatGPT на русском языке
https://gptunnel.ru/?ref=Anton
---------------------------------------------------
Донат для автора блога