Двойно свързани списъци и как да ги прилагаме в 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

По-малко очевидно изпълнение, за което се сетих, беше в играта Пасианс. Отстрани е изображение на пасианс терминологии, за да илюстрирам моето мнение.

Играта е блестящ пример, при който постоянно трябва да можете да преглеждате предишната и следващата карти, независимо дали това е на масата или купчината за отпадъци. Докато играете карта от купчината за отпадъци до масата, купчината за отпадъци се актуализира с картата преди това.

За по-оживено обсъждане на употребите в двойно свързани списъци бих препоръчал да разгледате тази дискусия на stackoverflow:

Така че следващия път, когато прилагате свързан списък, защо да не опитате двойно свързан? Не е много повече код отгоре на свързан списък и има дълбоки ползи!

Допълнителни ресурси

Пълна връзка към моята Python 3 реализация на двойно свързан списък може да се намери в моето репо за Github.

Ако искате триизмерна печатна верига от двойно свързани списъци, аз го качих в 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