Автор оригинала: Frank Hofmann.
Связанные списки Python
Связанный список-одна из наиболее распространенных структур данных, используемых в информатике. Он также является одним из самых простых и фундаментален для структур более высокого уровня, таких как стеки, циклические буферы и очереди.
Вообще говоря, список-это набор отдельных элементов данных, связанных ссылками. Программисты на языке Си знают это как указатели. Например, элемент данных может состоять из адресных данных, географических данных, геометрических данных, маршрутной информации или сведений о транзакциях. Обычно каждый элемент связанного списка имеет один и тот же тип данных, специфичный для данного списка.
Один элемент списка называется узлом. Узлы не похожи на массивы, которые последовательно хранятся в памяти. Вместо этого он, скорее всего, найдет их в разных сегментах памяти, которые вы можете найти, следуя указателям от одного узла к другому. Обычно конец списка помечается нулевым элементом, представленным эквивалентом Python None .
Рисунок 1: Односвязный список
Существует два вида списков – одинарные и двусвязные списки . Узел в односвязном списке указывает только на следующий элемент в списке, тогда как узел в двусвязном списке также указывает на предыдущий узел. Структура данных занимает больше места, потому что вам понадобится дополнительная переменная для хранения дальнейшей ссылки.
Рисунок 2: Двусвязный список
Односвязный список можно пройти от головы до хвоста, в то время как обратный путь не так прост. Напротив, двусвязный список позволяет обходить узлы в обоих направлениях с одинаковой стоимостью, независимо от того, с какого узла вы начинаете. Кроме того, добавление и удаление узлов, а также разбиение односвязных списков выполняется не более чем в два этапа. В двусвязном списке необходимо изменить четыре указателя.
Язык Python не содержит предопределенного типа данных для связанных списков. Чтобы справиться с этой ситуацией, мы должны либо создать свой собственный тип данных, либо использовать дополнительные модули Python, которые обеспечивают реализацию такого типа данных.
В этой статье мы рассмотрим шаги по созданию собственной структуры данных связанного списка. Сначала мы создаем соответствующую структуру данных для узла. Во-вторых, вы узнаете, как реализовать и использовать как односвязный список, так и, наконец, двусвязный список.
Шаг 1: Узел как структура данных
Чтобы иметь структуру данных, с которой мы можем работать, мы определяем узел. Узел реализуется как класс с именем ListNode . Класс содержит определение для создания экземпляра объекта, в данном случае с двумя переменными – data для сохранения значения узла и next для хранения ссылки на следующий узел в списке. Кроме того, узел имеет следующие методы и свойства:
__init_(): инициализировать узел с даннымиself.data: значение, хранящееся в узлеself.next: опорный указатель на следующий узелhas_value(): сравнение значения со значением узла
Эти методы гарантируют, что мы можем правильно инициализировать узел с нашими данными ( __init__ () ) и покрывать как извлечение данных, так и их хранение (через свойство self.data ), а также получение ссылки на подключенный узел (через свойство self.next ). Метод has_value() позволяет сравнить значение узла со значением другого узла.
Листинг 1: Класс ListNode
class ListNode:
def __init__(self, data):
"constructor to initiate this object"
# store data
self.data = data
# store reference (next item)
self.next = None
return
def has_value(self, value):
"method to compare the value with the node data"
if self.data == value:
return True
else:
return False
Создание узла так же просто, как и создание экземпляра объекта класса ListNode :
Листинг 2: Создание экземпляров узлов
node1 = ListNode(15)
node2 = ListNode(8.2)
node3 = ListNode("Berlin")
Сделав это, мы имеем в наличии три экземпляра класса ListNode . Эти экземпляры представляют собой три независимых узла, которые содержат значения 15 (целое число), 8.2 (поплавок) и “Берлин” (строка).
Шаг 2: Создание класса для односвязного списка
В качестве второго шага мы определяем класс с именем Single Linked List , который охватывает методы, необходимые для управления узлами списка. Он содержит эти методы:
__init__(): инициировать объектlist_length(): возвращает количество узловoutput_list(): выводит значения узловadd_list_item(): добавить узел в конец спискаunordered_search(): поиск в списке узлов с заданным значениемremove_list_item_by_id(): удалить узел в соответствии с его идентификатором
Мы рассмотрим каждый из этих методов шаг за шагом.
Метод __init__() определяет две внутренние переменные класса с именами head и tail . Они представляют собой начальный и конечный узлы списка. Изначально и head , и tail имеют значение None до тех пор, пока список пуст.
Листинг 3: Класс Single Linked List (часть первая)
class SingleLinkedList:
def __init__(self):
"constructor to initiate this object"
self.head = None
self.tail = None
return
Шаг 3: Добавление узлов
Добавление элементов в список осуществляется через add_list_item() . Этот метод требует узла в качестве дополнительного параметра. Чтобы убедиться, что это правильный узел (экземпляр класса ListNode ), параметр сначала проверяется с помощью встроенной функции Python isinstance() . В случае успеха узел будет добавлен в конец списка. Если item не является ListNode , то он создается.
В случае, если список (все еще) пуст, новый узел становится главой списка. Если узел уже находится в списке, то значение tail корректируется соответствующим образом.
Листинг 4: Класс Single Linked List (часть вторая)
def add_list_item(self, item):
"add an item at the end of the list"
if not isinstance(item, ListNode):
item = ListNode(item)
if self.head is None:
self.head = item
else:
self.tail.next = item
self.tail = item
return
Метод list_length() подсчитывает узлы и возвращает длину списка. Чтобы перейти от одного узла к следующему в списке, в игру вступает свойство узла self.next и возвращает ссылку на следующий узел. Подсчет узлов выполняется в цикле while до тех пор, пока мы не достигнем конца списка, который представлен ссылкой None на следующий узел.
Листинг 5: Класс Единого связанного списка (часть третья)
def list_length(self):
"returns the number of list items"
count = 0
current_node = self.head
while current_node is not None:
# increase counter by one
count = count + 1
# jump to the linked node
current_node = current_node.next
return count
Метод output_list() выводит значения узлов с помощью свойства node data . Опять же, для перехода от одного узла к другому используется ссылка, предоставляемая через свойство next .
Листинг 6: Класс Single Linked List (часть четвертая)
def output_list(self):
"outputs the list (the value of the node, actually)"
current_node = self.head
while current_node is not None:
print(current_node.data)
# jump to the linked node
current_node = current_node.next
return
На основе класса SingleLinkedList мы можем создать правильный список с именем track и играть с его методами , как уже описано выше в Listings 3-6 . Поэтому мы создаем четыре узла списка, оцениваем их в цикле for и выводим содержимое списка. Листинг 7 показывает, как это запрограммировать, а Листинг 8 показывает выходные данные.
Листинг 7: Создание узлов и вывод списка
# create four single nodes
node1 = ListNode(15)
node2 = ListNode(8.2)
item3 = "Berlin"
node4 = ListNode(15)
track = SingleLinkedList()
print("track length: %i" % track.list_length())
for current_item in [node1, node2, item3, node4]:
track.add_list_item(current_item)
print("track length: %i" % track.list_length())
track.output_list()
Вывод выглядит следующим образом и показывает, как растет список:
Листинг 8: Добавление узлов в список
$ python3 simple-list.py track length: 0 track length: 1 15 track length: 2 15 8.2 track length: 3 15 8.2 Berlin track length: 4 15 8.2 Berlin 15
Шаг 4: Поиск по списку
Поиск по всему списку осуществляется с помощью метода unordered_search() . Для поиска значения требуется дополнительный параметр. Глава списка-это отправная точка.
Во время поиска мы подсчитываем узлы. Чтобы указать совпадение, мы используем соответствующий номер узла. Метод unordered_search() возвращает список номеров узлов, представляющих совпадения. Например, и первый, и четвертый узел содержат значение 15. Поиск 15 результатов в списке с двумя элементами: [1, 4] .
Листинг 9: Метод поиска unordered_search()
def unordered_search (self, value):
"search the linked list for the node that has this value"
# define current_node
current_node = self.head
# define position
node_id = 1
# define list of results
results = []
while current_node is not None:
if current_node.has_value(value):
results.append(node_id)
# jump to the linked node
current_node = current_node.next
node_id = node_id + 1
return results
Шаг 5: Удаление элемента из списка
Удаление узла из списка требует корректировки только одной ссылки – та, которая указывает на удаляемый узел, теперь должна указывать на следующий. Эта ссылка хранится удаляемым узлом и должна быть заменена. В фоновом режиме сборщик мусора Python заботится о несвязанных объектах и приводит их в порядок.
Следующий метод называется remove_list_item_by_id() . В качестве параметра он ссылается на номер узла, аналогичный значению, возвращаемому функцией unordered_search() .
Листинг 10: Удаление узла по номеру узла
def remove_list_item_by_id(self, item_id):
"remove the list item with the item id"
current_id = 1
current_node = self.head
previous_node = None
while current_node is not None:
if current_id == item_id:
# if this is the first node (head)
if previous_node is not None:
previous_node.next = current_node.next
else:
self.head = current_node.next
# we don't have to look any further
return
# needed for the next iteration
previous_node = current_node
current_node = current_node.next
current_id = current_id + 1
return
Шаг 6: Создание Двусвязного списка
Чтобы создать двусвязный список, естественно просто расширить класс ListNode , создав дополнительную ссылку на предыдущий узел. Это влияет на методы добавления, удаления и сортировки узлов. Как показано в Листинге 11 , для хранения ссылочного указателя на предыдущий узел в списке было добавлено новое свойство с именем previous . Мы изменим наши методы, чтобы использовать это свойство также для отслеживания и обхода узлов.
Листинг 11: Класс узлов расширенного списка
class ListNode:
def __init__(self, data):
"constructor class to initiate this object"
# store data
self.data = data
# store reference (next item)
self.next = None
# store reference (previous item)
self.previous = None
return
def has_value(self, value):
"method to compare the value with the node data"
if self.data == value:
return True
else:
return False
Теперь мы можем определить двусвязный список следующим образом:
Листинг 12: Класс Двойного Связанного списка
class DoubleLinkedList:
def __init__(self):
"constructor to initiate this object"
self.head = None
self.tail = None
return
def list_length(self):
"returns the number of list items"
count = 0
current_node = self.head
while current_node is not None:
# increase counter by one
count = count + 1
# jump to the linked node
current_node = current_node.next
return count
def output_list(self):
"outputs the list (the value of the node, actually)"
current_node = self.head
while current_node is not None:
print(current_node.data)
# jump to the linked node
current_node = current_node.next
return
def unordered_search (self, value):
"search the linked list for the node that has this value"
# define current_node
current_node = self.head
# define position
node_id = 1
# define list of results
results = []
while current_node is not None:
if current_node.has_value(value):
results.append(node_id)
# jump to the linked node
current_node = current_node.next
node_id = node_id + 1
return results
Как было описано ранее, добавление узлов требует немного больше действий. Листинг 13 показывает, как это реализовать:
Листинг 13: Добавление узлов в двусвязный список
def add_list_item(self, item):
"add an item at the end of the list"
if isinstance(item, ListNode):
if self.head is None:
self.head = item
item.previous = None
item.next = None
self.tail = item
else:
self.tail.next = item
item.previous = self.tail
self.tail = item
return
При удалении элемента из списка необходимо учитывать аналогичные затраты. Листинг 14 показывает, как это сделать:
Листинг 14: Удаление элемента из двусвязного списка
def remove_list_item_by_id(self, item_id):
"remove the list item with the item id"
current_id = 1
current_node = self.head
while current_node is not None:
previous_node = current_node.previous
next_node = current_node.next
if current_id == item_id:
# if this is the first node (head)
if previous_node is not None:
previous_node.next = next_node
if next_node is not None:
next_node.previous = previous_node
else:
self.head = next_node
if next_node is not None:
next_node.previous = None
# we don't have to look any further
return
# needed for the next iteration
current_node = next_node
current_id = current_id + 1
return
В листинге 15 показано, как использовать класс в программе Python.
Листинг 15: Построение двусвязного списка
# create three single nodes
node1 = ListNode(15)
node2 = ListNode(8.2)
node3 = ListNode("Berlin")
node4 = ListNode(15)
track = DoubleLinkedList()
print("track length: %i" % track.list_length())
for current_node in [node1, node2, node3, node4]:
track.add_list_item(current_node)
print("track length: %i" % track.list_length())
track.output_list()
results = track.unordered_search(15)
print(results)
track.remove_list_item_by_id(4)
track.output_list()
Как вы можете видеть, мы можем использовать класс точно так же, как и раньше, когда он был просто односвязным списком. Единственное изменение – это внутренняя структура данных.
Шаг 7: Создание Двусвязных списков с помощью deque
Поскольку другие инженеры столкнулись с той же проблемой, мы можем упростить вещи для себя и использовать одну из немногих существующих реализаций. В Python мы можем использовать объект deque из модуля collections . Согласно документации модуля:
Деки-это обобщение стеков и очередей (название произносится как “колода” и является сокращением от “двусторонняя очередь”). Deques поддерживают потокобезопасные, эффективные с точки зрения памяти приложения и всплывающие окна с обеих сторон deque с примерно одинаковой производительностью O(1) в любом направлении.
Например, этот объект содержит следующие методы:
append(): добавить элемент в правую часть списка (конец)append_left(): добавить элемент в левую часть списка (head)clear(): удалить все элементы из спискаcount(): подсчет количества элементов с определенным значениемcount(): подсчет количества элементов с определенным значениемcount(): подсчет количества элементов с определенным значениемpop(): удаление элемента из правой части списка (конец)pop left(): удаление элемента из левой части списка (head)remove(): удаление элемента из спискаreverse(): перевернуть список
Базовая структура данных deque представляет собой список Python, который является двусвязным. Первый узел списка имеет индекс 0. Использование deque приводит к значительному упрощению класса ListNode . Единственное, что мы сохраняем, – это переменная класса data для хранения значения узла. Листинг 16 выглядит следующим образом:
Листинг 16: Класс ListNode с deque (упрощенный)
from collections import deque
class ListNode:
def __init__(self, data):
"constructor class to initiate this object"
# store data
self.data = data
return
Определение узлов не меняется и аналогично Листингу 2 . С учетом этих знаний мы создаем список узлов следующим образом:
Листинг 17: Создание списка с помощью deque
track = deque([node1, node2, node3])
print("three items (initial list):")
for item in track:
print(item.data)
Добавление элемента в начало списка работает с помощью метода append_left() как показано в листинге 18 :
Листинг 18: Добавление элемента в начало списка
# add an item at the beginning
node4 = ListNode(15)
track.append_left(node4)
print("four items (added as the head):")
for item in track:
print(item.data)
Аналогично, append() добавляет узел в конец списка, как показано в Листинге 19 :
Листинг 19: Добавление элемента в конец списка
# add an item at the end
node5 = ListNode("Moscow")
print("five items (added at the end):")
track.append(node5)
for item in track:
print(item.data)
Вывод
Связанные списки как структуры данных просты в реализации и обеспечивают большую гибкость использования. Это делается с помощью нескольких строк кода. В качестве улучшения вы можете добавить счетчик узлов – переменную класса, которая просто содержит количество узлов в списке. Это уменьшает определение длины списка до одной операции с O(1), и вам не нужно проходить весь список.
Для дальнейшего чтения и альтернативных реализаций вы можете посмотреть здесь:
list– Типы данных связанного списка для Python ( https://pythonhosted.org/llist/ )коллекции– Контейнерные типы данных ( https://docs.python.org/3.6/library/collections.html )
Признание
Автор хотел бы поблагодарить Герольда Рупрехта и Мэнди Ноймайер за их поддержку и комментарии при подготовке этой статьи.