Связный список в Python
Ну что, соскучились по информатике? Отлично. Вон там, видите? Прямиком с первого курса программистских специальностей вам динамично машут своими связями связные списки. Вы с ними знакомы? Если нет, то пришла пора.
Связный список — это структура данных, которая состоит из элементов (узлов). В узлах хранятся данные, а между собой узлы соединены связями. Связь — это ссылка на следующий или предыдущий элемент списка.
Таким образом, узел состоит из данных и одной/двух связей, а сам связный список — из узлов.
Область применения и значимость таких списков в мире программирования огромны. На их основе создаются многие другие структуры данных (например, очереди, графы и стеки).
Главной задачей связных списков является динамический доступ и хранение произвольного количества данных
Ключевые слова здесь "динамический" и "произвольный".
Работая с python-коллекциями, вы вряд ли столкнётесь с проблемами, которые возникали, скажем, у C++ программистов при выборе структуры данных для хранения нескольких объектов. Не углубляясь в дебри, варианты были следующие: массив, динамический массив и связный список.
Обычный массив вполне подходил в случае, когда количество элементов было заранее определено и фиксировано. Но если число объектов было произвольным, возникали трудности. Добавить или удалить элемент из такого массива было невозможно. Таким образом, вполне естественным был выбор динамического массива.
Динамический массив умеет менять свой размер
По сути — это обычный массив с парой дополнительных показателей. Первый показатель — текущая длина массива, а второй — его максимальный размер. Когда, при добавлении элементов, текущая длина превышала максимальную, обычный массив внутри динамического пересоздавался на структуру большего размера, а все существующие элементы сдвигались на число добавленных.
Таким образом, если элементы добавлялись в начало, то приходилось сдвигать весь старый массив, что, очевидно, являлось затратным и нерациональным действом. Вдобавок к этому, в C/C++ ещё и возникали проблемы с указателями, который из-за сдвига становились недействительными. Следовательно, если требовалась частая вставка новых элементов (причём не только в конец), появлялась необходимость использования более гибкой структуры данных. Этой структурой данных являлся связный список.
👉 Связный список отличается от массива тем, что массив хранится в непрерывном блоке памяти, в то время, как для узлов списка порядок расположения их в памяти не обязан совпадать с текущим внутренним.
Отсюда вытекает наиболее значимый плюс связных списков. При удалении или добавлении элементов никаких смещений не происходит: гибкие ссылочные связи рвутся и добавляются достаточно быстро, поэтому скорость этой операции гораздо выше, чем для динамического массива.
Но в этом же кроется и главный недостаток списков. Из-за непоследовательного расположения узлов в памяти, возникает очевидная сложность прямого доступа к элементу и определения фактического адреса по его индексу. Чтобы обратиться к произвольному объекту списка, требуется обойти все предшествующие ему элементы. Для динамического же массива такая операция выполняется за константное время.
Как работает LinkedList в Python
В Python нет такой структуры данных, как связный список
Обычные lists созданы на основе массивов и хранятся в памяти одним блоком. Однако в модуле collections есть такая штука, как дек (deque) или двусторонняя очередь. Вот она-то как раз и способна покрыть любую вашу необходимость в использовании