Связный список в Python

Содержание

Как работает LinkedList в Python
Работа со связным списком

Создание
Цикл по списку
Содержится ли элемент в списке
Добавление элемента и удаление элемента

Ну что, соскучились по информатике? Отлично. Вон там, видите? Прямиком с первого курса программистских специальностей вам динамично машут своими связями связные списки. Вы с ними знакомы? Если нет, то пришла пора.

Таким образом, узел состоит из данных и одной/двух связей, а сам связный список — из узлов.

Область применения и значимость таких списков в мире программирования огромны. На их основе создаются многие другие структуры данных (например, очереди, графы и стеки).

Главной задачей связных списков является динамический доступ и хранение произвольного количества данных

Ключевые слова здесь "динамический" и "произвольный".

Работая с python-коллекциями, вы вряд ли столкнётесь с проблемами, которые возникали, скажем, у C++ программистов при выборе структуры данных для хранения нескольких объектов. Не углубляясь в дебри, варианты были следующие: массив, динамический массив и связный список.

Обычный массив вполне подходил в случае, когда количество элементов было заранее определено и фиксировано. Но если число объектов было произвольным, возникали трудности. Добавить или удалить элемент из такого массива было невозможно. Таким образом, вполне естественным был выбор динамического массива.

Динамический массив умеет менять свой размер

По сути — это обычный массив с парой дополнительных показателей. Первый показатель — текущая длина массива, а второй — его максимальный размер. Когда, при добавлении элементов, текущая длина превышала максимальную, обычный массив внутри динамического пересоздавался на структуру большего размера, а все существующие элементы сдвигались на число добавленных.

Таким образом, если элементы добавлялись в начало, то приходилось сдвигать весь старый массив, что, очевидно, являлось затратным и нерациональным действом. Вдобавок к этому, в C/C++ ещё и возникали проблемы с указателями, который из-за сдвига становились недействительными. Следовательно, если требовалась частая вставка новых элементов (причём не только в конец), появлялась необходимость использования более гибкой структуры данных. Этой структурой данных являлся связный список.

👉 Связный список отличается от массива тем, что массив хранится в непрерывном блоке памяти, в то время, как для узлов списка порядок расположения их в памяти не обязан совпадать с текущим внутренним.

Отсюда вытекает наиболее значимый плюс связных списков. При удалении или добавлении элементов никаких смещений не происходит: гибкие ссылочные связи рвутся и добавляются достаточно быстро, поэтому скорость этой операции гораздо выше, чем для динамического массива.

Но в этом же кроется и главный недостаток списков. Из-за непоследовательного расположения узлов в памяти, возникает очевидная сложность прямого доступа к элементу и определения фактического адреса по его индексу. Чтобы обратиться к произвольному объекту списка, требуется обойти все предшествующие ему элементы. Для динамического же массива такая операция выполняется за константное время.

Как работает LinkedList в Python

В Python нет такой структуры данных, как связный список

Обычные lists созданы на основе массивов и хранятся в памяти одним блоком. Однако в модуле collections есть такая штука, как дек (deque) или двусторонняя очередь. Вот она-то как раз и способна покрыть любую вашу необходимость в использовании LinkedList-ов. В частности, используя дек, можно вставлять или удалять элементы, как с начала, так и с конца списка с константной производительностью. Итак, посмотрим на некоторые возможности дека.

Работа со связным списком

Создание

Сначала создадим его экземпляр. Для этого нужно импортировать соответствующую библиотеку:

from collections import deque
obj_deque = deque()

print(type(obj_deque))
> <class 'collections.deque'>

Библиотеку импортировали, объект создали. Отлично. Стоит иметь в виду, что в качестве аргумента функция deque() принимает только итерируемые объекты. Таким образом, дек можно сразу же инициализировать:

# аргумент-строка
fd = deque('string')
# аргумент-список
sd = deque(['l', 'i', 's', 't'])
 
print(fd)
> deque(['s', 't', 'r', 'i', 'n', 'g'])
 
print(sd)
> deque(['l', 'i', 's', 't'])

А теперь, смотрите:

# аргумент - число с плавающей точкой
td = deque(36.6)

> 
Traceback (most recent call last):
 td = deque(36.6)
TypeError: 'float' object is not iterable

Ошибка произошла из-за того, что в функцию мы передали число, которое, конечно же, не является итерируемым объектом.

Цикл по списку

Дек это обычная коллекция, поэтому обход её элементов совершаем при помощи цикла for:

digits = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
# выведем квадраты чисел от 1 до 10
for d in digits:
    print(d ** 2, end=' ')
 
> 1 4 9 16 25 36 49 64 81

Содержится ли элемент в списке

Проверить, содержится ли в деке тот или иной элемент, можно воспользовавшись методом __contains__:

onepiece = deque(['Luffy', 'Zoro', 'Nami', 'Usopp', 'Chopper', 'Sanji', 'Franky', 'Robin', 'Brook'])

print(onepiece.__contains__('Luffy'))
> True
 
print(onepiece.__contains__('Flamingo'))
> False

Добавление элемента и удаление элемента

После инициализации дека можно делать с ним всякие разные вещи, например, добавлять элементы в его конец и удалять их оттуда:

# создали дек
brokilon = deque(['driad', 'wood', 'scoiatael'])
print(brokilon)
> deque(['driad', 'wood', 'scoiatael'])

# добавили элемент в конец
brokilon.append('witcher')
print(brokilon)
> deque(['driad', 'wood', 'scoiatael', 'witcher'])
 
# удалили элемент с конца
brokilon.pop()
print(brokilon)
> deque(['driad', 'wood', 'scoiatael'])

Проделаем аналогичные операции, с той лишь разницей, что добавлять и удалять элементы будем из начала дека:

prime_evil = deque(['Baal', 'Diablo'])
print(prime_evil)
> deque(['Baal', 'Diablo'])
 
prime_evil.appendleft('Mephisto')
print(prime_evil)
> deque(['Mephisto', 'Baal', 'Diablo'])
 
prime_evil.popleft()
print(prime_evil)
> deque(['Baal', 'Diablo'])

Прекрасно видно, что всё работает так, как надо: элемент добавился и удалился именно из начала. Сложность вычислений нетрудно проверить самостоятельно, сделав необходимые замеры, однако можете поверить — на этих операциях она равна О(1).

Хоть дек и удовлетворяет всем требованиям, которые вы могли бы ожидать от связного списка, по большому счёту — это другая структура данных. Но, раз уж мы говорим о связных списках, которых в Питоне нет, то как же быть?

Ответ прост: если где-то чего-то нет, то совсем не значит, что это нельзя создать! И да, в Python действительно можно без особых проблем реализовать связный список. Другой вопрос — нужен ли он вам, кроме как для улучшения своих навыков программирования или подготовки к собеседованию?