Научитесь реализовывать одну из самых важных структур данных в Python.
Связанные списки, как и массивы, представляют собой структуры данных, которые используются для хранения множества элементов. Но в отличие от массивов связанные списки не хранятся в непрерывном месте в памяти. Вместо этого они используют узлы, которые могут храниться в любом месте памяти, но связаны друг с другом с помощью указателей. Каждый узел содержит ссылку на следующий узел в связанном списке.
Class node:
def __init__(self,data) -> None:
self.data = data
self.next_node = None
Создание связанного списка
Чтобы создать связанный список, все, что нам нужно знать, это первый узел, поскольку каждый узел в связанном списке указывает на следующий, а последний узел указывает на ноль, указывая на конец связанного списка.
Class linked_list :
def __init__(self,first_node = None) -> None:
self. first_node = first_node
node1 = node('first')
node2 = node('second')
node3 = node('third')
linked_list1= linked_list(node1)
node1.next_node = node2
node2.next_node = node3
Вот как вы создаете простой связанный список, содержащий 3 элемента, не так ли? хорошо, может быть, это не так просто, как создание массива, но, как вы узнаете позже, это может быть очень полезно и стоит вашего времени.
Обход связанного списка
Поскольку связанные списки не хранятся в легко определяемых местах памяти, компьютер не может перейти к третьему элементу, не просмотрев первый и второй элементы, следовательно, необходимо перемещаться по каждому элементу в связанном списке, чтобы выполнить операция на нем. Это называется обходом связанного списка
def read(self,index):
current_node = self.first_node
current_index = 0
while current_index < index:
current_node = current_node.next_node
current_index += 1
if current_node == None :
return None
return current_node
Функция чтения — это форма обхода, при которой мы возвращаем узел в заданном индексе. Эта форма обхода полезна в других операциях.
Поиск элемента в связанном списке
При проверке того, находится ли элемент в связанном списке, мы должны просмотреть каждый элемент в связанном списке и сравнить его со значением, которое мы ищем.
def search(self,data):
current_node = self.first_node
current_index = 0
while current_node:
if current_node.data == data:
return current_index
else:
current_node = current_node.next_node
current_index += 1
return None
Вставка элементов в связанный список
Помните немного о том, что массивы хранятся в непрерывном месте? хорошо, это работает хорошо, пока нам не нужно вставить элемент в массив. Допустим, мы хотим вставить x в 3-й индекс массива из 20 элементов, нам нужно будет сдвинуть каждый элемент из 3-го элемента на один пробел вперед, что не очень быстро. Вставка в массив выполняется быстрее всего в конце и медленнее всего в начале, а для связанного списка дело обстоит наоборот. Фактически, для вставки в начало связанного списка требуется всего один шаг, что с точки зрения скорости настолько быстро, насколько это возможно.
Вставка в связанные списки выполняется путем изменения next_node нового узла на узел после заданного индекса и next_node предыдущего узла на новый узел.
def insert(self,value,index):
previous_node = self.read(index-1)
next_node = previous_node.next_node
current_node = node(value,next_node)
previous_node.next_node = current_node
Для вставки в начале требуется только изменить first_node на новый узел и связать его с предыдущим first_node.
def insert_at_beginning(self,value):
old_node = self.first_node
self.first_node = node(value)
self.first_node.next_node = old_node
Удаление элементов в связанном списке
Как и при вставке, удаление элемента выполняется путем изменения связей между узлами.
def delete(self,index):
node_before = self.read(index-1)
current_node = node_before.next_node
node_after = current_node.next_node
node_before.next_node = node_after
В приведенном выше примере мы пытаемся удалить узел с заданным индексом, получая узел до и после него, а не связывая их друг с другом.
Чтобы удалить в начале, все, что нам нужно сделать, это изменить first_node на его next_node.
def delete_at_beginning(self,index):
self.first_node = self.first_node.next_node
Зачем использовать связанный список?
Как вы могли догадаться, связанные списки в целом не превосходят массивы. Вместо этого они лучше подходят для операций вставки и удаления и очень полезны, когда у вас есть большие наборы данных, которые будут сильно изменены при их использовании. Это может сэкономить много времени, так как не нужно будет перемещать элементы, как в массиве.
Важно научиться использовать преимущества уникальных сильных и слабых сторон каждой структуры данных при попытке решить проблемы или подготовиться к интервью.
Спасибо за прочтение. Я надеюсь, что это было полезно. Дайте мне знать в комментариях, если у вас есть какие-либо вопросы или комментарии, чтобы добавить. Я буду ждать вашего ответа.
Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter и LinkedIn. Присоединяйтесь к нашему сообществу Discord.
