Подвійно пов'язані списки та як їх реалізувати в 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

Менш очевидна реалізація, про яку я думав, була в грі Пасьянс. Збоку - зображення термінології "Пасьянс", яка допоможе проілюструвати мою думку.

Гра - яскравий приклад, коли вам постійно потрібно мати можливість переглядати попередню та наступну карти, будь то на столі або в купі сміття. Коли ви граєте в карту зі сміттєвої маси до столу, купа сміття оновлюється попередньою карткою.

Для більш активного обговорення використання в подвійно пов'язаних списках я рекомендую ознайомитись із цією дискусією на стадії потоку:

Тож наступного разу, коли ви реалізуєте зв’язаний список, чому б не спробувати подвійно пов'язаний? Це не так вже й багато коду на верхній частині пов'язаного списку, і є глибокі переваги!

Додаткові ресурси

Повне посилання на мою реалізацію подвійного списку 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