Структура данных «Связный список». Представление в памяти, сложность операций. Сравнение с массивом. Двусвязный список.
В прошлом уроке вы узнали, какая сложность у операций поиска, вставки и удаления при работе с массивами.
В Python массив называется списком (не путайте со связным списком). Если вы писали, например, на С++, это может вас запутать. В С++ и в некоторых других языках программирования такую структуру данных называют «массив».
Элементы массива в памяти компьютера расположены последовательно. Чтобы вставить или удалить элемент из начала списка, нужно O(n) операций. Придётся передвигать все остальные элементы.
Вот бы иметь структуру данных, в которой при вставке или удалении элемента передвигать остальные не нужно.
Такая структура существует. Она называется «Связный список». Очень часто в стандартной библиотеке языков программирования её реализации нет. Хотя, например, в Java есть соответствующий класс LinkedList.
Связные списки несложно реализовать самостоятельно, и вы, вероятно, будете решать задачи со связными списками на собеседованиях.
В связном списке каждый элемент имеет значение и ссылку на следующий элемент списка. За исключением последнего — он ссылается на None, нулевой указатель или аналогичный объект, в зависимости от языка программирования.
Предположим, вы хотите вставить новый элемент между первым и вторым. Для этого нужно, чтобы первый элемент теперь указывал на новый, а новый — на второй, ставший теперь третьим.
Все просто: берём и переставляем указатели.
Концепцию указателей применяют не во всех языках программирования. И для понимания принципа работы связных списков в указателях разбираться необязательно.
Рассмотрим, как эта идея работает, на примере.
Кузен Риты Петя Первищенко служит в армии. Сержант Первищенко получил в своё командование новый взвод и строит его, чтобы назначить дежурных по кухне. Строй начинается от двери, рядовые встают по росту. Солдаты плохо запоминают даты, так как большинство их дней проходят примерно одинаково. Зато они хорошо запоминают поход в столовую и знают, кто дежурный. Чтобы солдату понять, когда он дежурит, достаточно запомнить, за кем он в строю. Всё просто: завтра дежурит первый, а затем все по очереди.
Но тут прибегает опоздавший очень высокого роста. Его место в начале строя. Нужно перестроить солдат так, чтобы сохранить требования: все должны стоять по росту, между солдатами должно быть определённое расстояние, и строй должен начинаться с фиксированного места. Поэтому опоздавший встаёт в строй в соответствии со своим ростом, а остальные двигаются на одну позицию в сторону. Если солдат в строю всего n, придётся проделать до n перестановок.
Итак, строй вновь сформирован. Но как же список дежурств? Неужели нужно сделать так же много действий? Нет! Опоздавшему достаточно запомнить, за кем он идёт в строю, а следующему после него солдату — что теперь он дежурит после опоздавшего.
Если опоздавший самый высокий, то ему нужно запомнить, что он в строю первый.
Случай с построением солдат иллюстрирует операцию добавление элемента в произвольное место в списке. Пример с графиком дежурств — в связный список.
В памяти компьютера элементы связного списка расположены в произвольных местах, а не по порядку, как в случае с массивом. Очень удобно!
Операция удаления работает похоже. Например, из связного списка нужно удалить третий элемент. Тогда переставляем указатель второго на четвёртый, если в списке больше трёх элементов. Если в списке три элемента, поставим указатель второго элемента на None либо аналогичный объект, в зависимости от языка программирования.
Чтобы представить эту структуру данных в С++, можно применять структуры, а в Python — классы. Рассмотрим код на Python.
Скопировать кодPYTHONclass Node:
def __init__(self, value = None, next = None):
self.value = value
self.next = next
def __str__(self):
return self.value У каждого элемента есть значение и ссылка на следующий элемент списка.
Метод str в Python определяет, что будет выведено при вызове функции print(). Тут мы его применяем для удобства. Он помогает выводить значение поля value в удобном формате. Метод str или аналогичный в другом языке программирования определять необязательно.
Создадим три элемента:
Скопировать кодPYTHONn3 = Node('third')
n2 = Node('second', n3)
n1 = Node('first', n2) Получили связный список из трёх элементов. Первый ссылается на второй:
Скопировать кодPYTHONprint(n1.next) # second Второй ссылается на третий, а третий — на None:
Скопировать кодPYTHONprint(n3.next) # None Так можно представлять связный список. Напишем функцию добавления нового элемента в связный список:
Скопировать кодPYTHONdef insert_node(node, index, value):
head = node
new_node = Node(value)
if index == 0:
new_node.next = node
return new_node
while index-1:
node = node.next
index -= 1
tmp = node.next
node.next = new_node
new_node.next = tmp
return head Что происходит в коде этой функции?
На вход она принимает голову списка, индекс, по которому вы хотите добавить элемент, и значение нового элемента. Возвращать функция будет голову списка.
Запомним голову списка в переменной head, чтобы потом вернуть её из функции. Сначала создадим объект класса Node из добавляемого элемента, так как все элементы в списке должны иметь два поля: значение и ссылку на соседа. Это нам и обеспечит класс Node.
Как вы, вероятно, догадались, нужно найти элемент, за которым хотим вставить новый, и переместить его указатель на вставляемый элемент. Новый элемент должен указывать на прошлого соседа того элемента, после которого мы сделали вставку.
Отдельно нужно обработать случай, когда хотим вставить элемент в голову списка, так как на неё никакой элемент не указывает. Добавляем новый элемент в качестве головы списка. Он будет ссылаться на предыдущую голову.
На первой итерации цикла переменная index-1 будет равна 1, и мы переместимся вправо на элемент с индексом 1. После этого элемента мы и хотим добавить новый. На второй итерации переменная index-1 будет равна 0, блок кода внутри цикла выполняться не будет. Как раз это нам и нужно, так как до нужной позиции мы уже дошли.
Затем меняем указатели. Элемент, на который указывал найденный объект, запомним во временную переменную. Это нужно сделать, потому что мы переставим указывающую на него ссылку. А терять этот элемент нельзя, ведь на него будет указывать вставляемый элемент. Поменяв ссылки, можем вернуть голову списка из функции.
Вставим элемент со значением 'new_node' на позицию 2:
Скопировать кодPYTHONnode, index, value = n1, 2, 'new_node'
head = insert_node(node, index, value) Посмотрим на голову списка. Она не изменилась.
Скопировать кодPYTHONprint(head) # first Элемент на позиции 1 также остался прежним.
Скопировать кодPYTHONprint(head.next) # second А вот элемент на позиции 2 поменялся. Теперь там объект класса Node со значением 'new_node', как мы и хотели.
Скопировать кодPYTHONprint(head.next.next) # new_node Запустите код с различными параметрами функции и посмотрите, что будет происходить.
Односвязный список — очень удобная структура данных, ведь в неё можно вставлять и удалять элементы очень эффективно.
Но получить доступ к элементу по индексу при использовании односвязного списка нельзя.
Есть модификация односвязного списка, которая позволяет двигаться в обоих направлениях — двусвязный список. Каждый его элемент, помимо ссылки на следующий элемент, имеет ссылку на предыдущий.
Чтобы ещё лучше разобраться в связных списках, выполните задания.
Решите задачи E, F, G и H из контеста.