И снова здравствуйте! В ожидании начала курса «Разработчик Python» Мы подготовили для вас небольшой оригинальный материал о связанных списках в Python.
Python — очень удобный и универсальный язык, но по умолчанию в нем нет такой структуры данных, как связанный список или LinkedList. Сегодня я поделюсь своей работой на эту тему и немного расскажу о том, что представляет собой эта структура данных.Эта статья будет интересна тем, кто плохо знаком с темой связанных списков и хочет понять, как они работают с алгоритмической точки зрения.
Что такое LinkedList?
LinkedList или связанный список — это структура данных.Связанный список предоставляет возможность создать двунаправленную очередь из любых элементов.
Каждый элемент такого списка считается узлом.
Фактически узел содержит свое значение, а также две ссылки — на предыдущий и на последующие узлы.
То есть список «связан» узлами, которые помогают перемещаться по списку вверх или вниз.
Благодаря этим структурным особенностям связанный список может быть организован в виде стека, очереди или двойной очереди.
Давайте визуализируем сухие определения.
Теперь у нас есть кошки, которые сидят в коробках.
И на каждой коробочке написано, в каком порядке она находится и что она должна обозначать.
Что мы будем делать со связанным списком: Проверьте, содержит ли он тот или иной элемент;
Добавьте узлы в конец;
Получить значение узла по индексу;
Удалить узлы.
На самом деле вариантов работы с ними гораздо больше, но мы сосредоточимся на реализации этих основных шагов.
Как только вы поймете принцип, по которому они построены, вы сможете легко реализовать свои собственные методы.
Вам придется начать с создания двух классов:
В общем, у нас есть узел, внутри которого есть какое-то значение — кот, и ссылка на следующий узел.class Box: def __init__ (self,cat = None): self.cat = cat self.nextcat = None class LinkedList: def __init__(self): self.head = None
То есть в классе Box соответственно есть кот и ссылка на следующий ящик.
Как и любой список, связанный список также имеет начало, а именно заголовок.
Поскольку изначально там ничего нет, для начального элемента установлено значение None.
Содержится ли элемент в списке
Начнем с чего-то простого.
Чтобы проверить, находится ли конкретный кот в одном из последовательных ящиков, нужно пройтись по всему списку, сверяя существующее значение со значениями элемента в списке.
def contains (self, cat):
lastbox = self.head
while (lastbox):
if cat == lastbox.cat:
return True
else:
lastbox = lastbox.nextcat
return False
Добавить узел в конец списка
Для начала вам нужно создать новый ящик и поместить в него нового кота.
Затем нужно проверить, начиная с начала связанного списка, есть ли у текущего узла ссылка на следующий и если она есть, то перейти к нему, иначе узел последний, а значит нужно создайте ссылку на следующий узел и поместите в него тот новый ящик, который мы создали.
def addToEnd(self, newcat):
newbox = Box(newcat)
if self.head is None:
self.head = newbox
return
lastbox = self.head
while (lastbox.nextcat):
lastbox = lastbox.nextcat
lastbox.nextcat = newbox
Получить узел по индексу
С помощью индекса catIndex мы хотим получить бокс-узел, но так как индекса как такового у узлов нет, то нужно придумать какую-то замену, а именно переменную, которая будет выполнять роль индекса.
Эта переменная — boxIndex. Проходим по всему списку и проверяем «порядковый номер» узла и, если он соответствует требуемому индексу, выдаем результат. def get(self, catIndex):
lastbox = self.head
boxIndex = 0
while boxIndex <= catIndex:
if boxIndex == catIndex:
return lastbox.cat
boxIndex = boxIndex + 1
lastbox = lastbox.nextcat
Удалить узел
Здесь мы рассмотрим удаление элемента не по индексу, а по значению, чтобы добавить хоть какое-то разнообразие.
Поиск начинается с начала списка, то есть с первого ящика, и продолжается до тех пор, пока ящиков не останется, то есть пока headcat не станет None. Мы проверяем, соответствует ли значение, хранящееся в текущем узле, тому, которое мы хотим удалить.
Если нет, то мы просто идем дальше.
Однако, если он совпадает, мы удаляем его и «перепривязываем» связи, то есть удаляем N-й блок, при этом блок N-1 теперь связывается с блоком N+1. def removeBox(self,rmcat):
headcat = self.head
if headcat is not None:
if headcat.cat==rmcat:
self.head = headcat.nextcat
headcat = None
return
while headcat is not None:
if headcat.cat==rmcat:
break
lastcat = headcat
headcat = headcat.nextcat
if headcat == None:
return
lastcat.nextcat = headcat.nextcat
headcat = None
На этом все, спасибо за прочтение материала! На самом деле структура LinkedList несложная, и важно понимать, как она работает изнутри.
Конечно, в Python это можно было бы реализовать в лямбда-выражениях, места это заняло бы гораздо меньше, но здесь я стремился как можно подробнее объяснить его структуру и принцип работы в Python, а не гнаться за оптимизацией.
Исходный код доступен посмотреть здесь .
Теги: #python #программирование #linkedlist
-
Взгляните На Ноутбук Sony Vaio Vpcz-124Gx/B
19 Oct, 24 -
«Умные» Рекламные Щиты
19 Oct, 24 -
Рынок Электронных Книг Растёт: Версия Pvi
19 Oct, 24 -
Про Макбук И Как Я Зашёл В Офис Хабра
19 Oct, 24
