Связанные списки - это линейный способ хранения данных. Он состоит из узлов, содержащих данные, а также указателей, указывающих, как перейти к следующему фрагменту данных. Думайте об узлах как об участнике цепочки. Каждая цепочка зависит друг от друга, чтобы поддерживать прочную связь. Если, например, в средней ссылке все отсутствует, после этого произойдет сбой. Это уже не полная цепочка! Как это преобразовать в связанные списки? Если один из указателей отсутствует или неверен, остальные данные больше не могут быть прочитаны.
Однако тема этой статьи касается более универсальной версии связанных списков - двусвязного списка. По сравнению с обычным (или односвязным) списком двусвязный список включает другой указатель, называемый предыдущим. Как вы могли догадаться, это позволяет узлу узнать, где находится предыдущий узел. Для сравнения, односвязный список должен снова пройти весь список до предыдущей точки, чтобы добраться до той же точки.
Информацию об односвязных списках можно найти в статье моего одноклассника:
Как упоминалось ранее, узлы указывают на другие места в памяти. Что это обозначает? Что ж, в отличие от массивов, которые хранятся в смежных местах, связанные списки просто имеют указатели. На схеме ниже каждый блок памяти (красный) имеет два указателя, указывающих на него. Он получает доступ к этой информации, глядя на указатель Далее (черный). Если он хочет найти предыдущий блок, он будет смотреть на указатель Предыдущий (белый).
Так как же реализовать двусвязный список? 🤔 Вот как в Python 3
Просто добавьте .prev в свой класс Node. Теперь вы готовы приступить к реализации!
Преимущества 👍 - С кодом Python 3!
Каковы преимущества двусвязного списка перед односвязным? Что ж, с двусвязным списком вы можете перемещаться вперед и назад между вашими узлами. Это очень упрощает такие вещи, как вставка. В случае двусвязных списков вы просто переместите свой связанный список к нужному узлу, а затем вызовете предыдущий узел.
Недостатки 😢
Хотя в связанных списках есть много преимуществ, это не универсальное решение. Как и в случае со многими структурами данных и алгоритмами, этот инструмент должен быть в вашем арсенале. Одним из недостатков односвязного списка является большее потребление памяти, поскольку каждая ссылка в двусвязном списке должна отслеживать предыдущий указатель. Кроме того, за указанным указателем сложно уследить.
На самом деле я все еще в процессе их реализации. На момент написания статьи (апрель 2019 г.) это была моя вторая успешная реализация. Каждый раз становится немного проще, но мне все еще нужно рисовать диаграммы того, как предыдущий указатель взаимодействует со всеми моими другими функциями.
Но для чего это можно было бы использовать?
Я слышал, вы спросите. Вспомните каждый раз, когда вы видели предыдущее и следующее. Есть несколько очевидных и тонких способов их реализации.
А как насчет такого футляра, как музыкальный проигрыватель? У него есть очень явные кнопки перехода к следующему и предыдущему. Для переключения между этими двумя песнями можно использовать двусвязный список.
А как насчет браузера? У них также есть явные способы перехода назад и вперед между посещенными вами веб-страницами.
А теперь подумайте о своем текстовом редакторе или редакторе фотографий по своему выбору. Каждый раз, когда вы делаете ошибку, вы можете нажать CTRL (CMD для Mac) + Z, чтобы отменить последнее действие. Точно так же вы можете повторить то, что вы отменили, с помощью CTRL (CMD для Mac) + Y. Почему это звучит знакомо? Это также может быть реализовано с двусвязным списком! Предыдущий указатель указывает на действия, которые были выполнены, а также дает возможность повторить действия, если вы отмените слишком много.
Менее очевидная реализация, о которой я подумал, была в игре Solitaire. Сбоку есть изображение терминологии Solitaire, чтобы помочь проиллюстрировать мою точку зрения.
Игра является ярким примером, когда вам постоянно нужно иметь возможность просматривать предыдущие и следующие карты, будь то в таблице или в куче мусора. Когда вы разыгрываете карту из стопки отходов на игровое поле, стопка отходов обновляется предыдущей картой.
Для более живого обсуждения использования двусвязных списков я бы рекомендовал взглянуть на это обсуждение stackoverflow:
Итак, в следующий раз, когда вы будете использовать связанный список, почему бы не попробовать двусвязный? Не так уж много кода поверх связанного списка, и это дает огромные преимущества!
Дополнительные ресурсы
Полную ссылку на мою реализацию двусвязного списка в Python 3 можно найти в моем репозитории на Github.
Если вам нужна цепочка двусвязных списков для 3D-печати, я загрузил ее на Thingiverse.
Https://www.geeksforgeeks.org/doubly-linked-list/
Https://www.tutorialspoint.com/data_structures_algorithms/doubly_linked_list_algorithm.htm
