Дважды связанные списки и как их реализовать в Python 3

Связанные списки - это линейный способ хранения данных. Он состоит из узлов, которые содержат данные, а также указателей того, как перейти к следующему фрагменту данных. Думайте об узлах как о цепочке. Каждая цепь зависит друг от друга, чтобы сохранить прочную связь. Если, например, в средней ссылке все отсутствует, то после этого происходит сбой. Это уже не полная цепочка! Как это перевести на связанные списки? Если один из указателей отсутствует или неверен, остальные данные больше не могут быть прочитаны.

Неверная цепочка! Это сломало бы связанный список!

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

Для получения информации о односвязных списках, пожалуйста, посетите статью моего одноклассника:

Как упоминалось ранее, узлы указывают на другие места в памяти. Что это значит? Ну, в отличие от массивов, которые хранятся в смежных местах, связанные списки просто имеют указатели. На диаграмме ниже каждый блок памяти (красный) имеет два указателя, которые указывают на него. Он получает доступ к этой информации, глядя на следующий указатель (черный). Если он хочет найти предыдущий блок, он посмотрит на предыдущий указатель (белый).

Так как же реализовать двусвязный список? Вот как в Python 3

Просто добавьте .prev к вашему классу Node. Теперь вы готовы начать реализацию!

Преимущества - С кодом Python 3!

Каковы некоторые преимущества двусвязного списка над односвязным? Ну, с помощью двусвязного списка, вы можете перемещаться назад и вперед между узлами. Это делает вставку очень простой. С помощью двусвязных списков вы просто перемещаете свой связанный список к нужному узлу, а затем вызываете предыдущий узел.

Недостатки

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

На самом деле, я все еще практикую их реализацию. Это будет моя вторая успешная реализация на момент написания этой статьи (апрель 2019 года). Каждый раз становится немного легче, но мне все еще нужно рисовать диаграммы того, как предыдущий указатель взаимодействует со всеми другими моими функциями.

Но для чего это будет использовано?

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

Источник: https://pbs.twimg.com/media/DxzXvUKXgAAvmxx.jpg

А как в случае с музыкальным проигрывателем? У этого есть очень явная следующая и предыдущая кнопка. Дважды связанный список может быть использован для циклического переключения между этими двумя песнями.

Или как насчет браузера? У них также есть явные способы переходить назад и вперед между посещенными вами веб-страницами.

Теперь подумайте о вашем программном обеспечении для обработки текстов или фоторедакторе на ваш выбор. Каждый раз, когда вы делаете ошибку, вы можете нажать CTRL (CMD для Mac) + Z, чтобы отменить это последнее действие. Кроме того, вы можете повторить то, что вы отменили, с помощью CTRL (CMD для Mac) + Y. Теперь, почему это звучит знакомо? Это также может быть реализовано с помощью двусвязного списка! Предыдущий указатель указывает на действия, которые были выполнены, и в то же время возможность отменить действия, если вы отмените слишком много.

Источник: https://gfycat.com/brilliantbeautifuldassieИсточник: https://www.solitairecardgames.com/how-to-play-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

https://www.youtube.com/watch?v=JdQeNxWCguQ