Связанные списки в Python
Связанный список - это линейная структура данных, элементы которой не хранятся в непрерывном месте. Это означает, что связанный список содержит отдельные вакуоли, известные как «узлы», которые содержат данные, для которых они были созданы, и ссылку на другой узел в списке.
Некоторыми преимуществами связного списка являются его прерывистый характер и время чтения, никогда не превышающее O(n). Связанный список не нужно хранить постоянно, потому что он имеет ссылки, встроенные в каждый узел, для расположения следующего по порядку. Если в памяти вашего компьютера мало места, идеально подойдет связанный список, поскольку всю структуру не нужно хранить в одном месте. Это также означает, что чтение связанного списка является линейным, поскольку размер списка приближается к бесконечности.
Однако недостатки делают его особенным. Кроме того, если в список вносится добавление, необходимо обновить весь список, чтобы ссылки оставались правильными. Последовательный характер связанного списка означает, что произвольный доступ не разрешен. Каждый узел необходимо читать в том порядке, в котором он был создан, чтобы иметь доступ ко всей необходимой информации.
В этой статье мы рассмотрим концепцию единственных и двусвязных списков и некоторые общие вопросы интервью, которые могут появиться для каждого из них.
Односвязный список
Односвязный список состоит из нескольких узлов, каждый из которых содержит а) данные и б) ссылку на следующий узел.
На изображении выше мы видим макет связанного списка. Начиная слева и продвигаясь вправо, мы видим, что заголовок списка содержит данные и указатель на следующий узел. Этот шаблон продолжается до конца списка, где он не является узлом. Значение NULL означает, что список закончился.
Посмотрите ниже код для создания односвязного списка.
# Node class
class Node:
# Function to initialize the node object
def __init__(self, data):
self.data = data # Assign data
self.nextnode = None # Initialize next as null
a = Node(1) # declaring data in each node
b = Node(2)
c = Node(3)
a.nextnode = b # link first node to second node
b.nextnode = c # link second node to third node
a.next.value # will return the value of the next node b = 2
Двусвязный список
В двусвязном списке каждый узел содержит данные, ссылку на узел, после него, и ссылку на узел, предшествующий ему.
Разница между односвязным списком и двусвязным списком - это «предыдущие» стрелки, указанные на рисунке выше. Преимущества дополнительного указателя означают, что список можно перемещать в любом направлении при доступе к информации - это означает, что переход от узла 5 к узлу 8 может быть проще, чем обход с начала списка.
Новые узлы в начале и в конце списка называются «дозорными». Эти узлы заменяют значения NULL, которые вы видите выше. Они позволяют быстро вставлять или удалять вверху или внизу списка.
Посмотрите ниже код для двусвязного списка.
# Code to create the nodes for a doubly linked list
# A linked list node
class Node:
def __init__(self):
self.data = None # container of the data
self.next_node = None # standard pointer to next node
self.prev_node = None # pointer to previous node
# Creating each node
a = Node(1)
b = Node(2)
c = Node(3)
# Connect the nodes
# Connect nodes a & b to each other in both directions
a.next_node = b
b.prev_node = a
# Connect nodes b & c to each other in both directions
b.next_node = c
c.prev_node = b
"""
We could create a circularly linked list by connecting the head of the list
to the tail
"""
Теперь, когда у нас есть код, необходимый для создания связанных списков, давайте рассмотрим некоторые общие вопросы собеседования, варианты которых вы можете найти на Leetcode.
Вопросов
1. Сторнирование связанного списка
Создайте функцию, чтобы перевернуть связанный список на месте. Вы будете использовать заголовок исходного списка и возвращать заголовок перевернутого списка.
Уловка, стоящая за этой проблемой, заключается в том, что разворот должен происходить в постоянном пространстве. Поэтому мы не создаем новый список и не добавляем или не используем прокси. Это необходимо сделать, работая непосредственно с этим списком.
def reversal(head):
# set variables for the node position
current = head #
prev = None
next_node = None
# let's us know that we haven't reached the end of the list
while current:
# copy the pointer of the head before we override it
next_node = current.nextnode
# change the pointer to point at None (because it is the new tail)
current.nextnode = prev
# move us along on the list, current becomes previous
prev = current
# and the next node becomes the current node we are looking at
current = nextnode
return prev
Как объяснено в приведенном выше коде, мы, по сути, просто переключаем указатели для каждого узла. Входными данными является текущая глава связанного списка - или в наших примерах. Затем функция проходит через каждый узел и переключает направление атрибута nextnode. Посмотрите картинку ниже для дальнейшей визуализации.
Этот подход имеет то преимущество, что снижает затраты на память и впечатляет интервьюеров своей способностью работать без создания нового списка и удержания процесса на O(n) времени.
2. Связанный список с N-го до последнего узла
Создайте функцию, которая принимает головной узел и целое число n, а затем возвращает n-й и последний узел из списка.
Уловка для этой задачи состоит в том, чтобы пройти по списку двумя маркерами. Первый маркер выполняет итерацию и проверяет, действительно ли существует предпоследний узел. Второй маркер идет позади и заканчивается в этом узле.
def nth_last_node(n,head):
# create two pointers that both start at the head of the list
pointer_1 = head
pointer_2 = head
# we will iterate through the list, moving the right pointer
# until there are n-spaces between them
for i in range(n-1):
# edge case, if no nextnode, raise an error
if not pointer_1.nextnode:
raise LookupError('Error: Command continues past index of list')
# if not edge case, move the right pointer to next node
pointer_1 = pointer_1.nextnode
# now there is a n-size block between them
# as long as the right pointer does not reach the end of the list
# the left pointer will move
while pointer_1.nextnode:
# once the right pointer hits the end the left pointer has found the
# nth to last node from the end
pointer_2 = pointer_2.nextnode
pointer_1 = pointer_1.nextnode
# return the nth to last node
return pointer_2
Хотя код отлично справляется с созданием пространства между ними, давайте посмотрим на визуальный элемент.
Как вы можете видеть между первым и вторым шагами, идея состоит в том, что указатель 1 должен создавать расстояние между собой и указателем 2, равное n узлам. Как только это безопасно, два указателя могут перемещаться в унисон - указатель 1 проверяет, не закончился ли список, и указатель 2 готов к объявлению своей текущей позиции как n-го до последнего узла.
Вот и все. У нас были базовые основы того, что такое связанный список, и какие вопросы по нему можно задать.
Дмитрий Сергеев
17.11.2021 в 15:51
