Dobbelt forbundne lister og hvordan man implementerer dem i Python 3

Koblede lister er en lineær måde at lagre data på. Det består af noder, der indeholder data såvel som pegepunkter for, hvordan man kommer til det næste stykke data. Tænk på knudepunkter som et medlem af en kæde. Hver kæde afhænger af hinanden for at bevare en stærk bånd. Hvis for eksempel det midterste link mangler alt efter det mislykkes. Det er ikke længere en komplet kæde! Hvordan oversættes dette til linkede lister? Hvis et af pegeplanerne mangler eller er forkert, kan resten af ​​dataene ikke længere læses.

Ikke en gyldig kæde! Dette ville bryde en sammenkoblet liste!

Emnet for denne artikel er imidlertid på en mere alsidig version af linkede lister - den dobbeltkædede liste. Sammenlignet med en almindelig (eller enkeltvis) linket liste inkluderer en dobbeltkædet liste en anden pointer kaldet forrige. Som du måske gætter, giver dette noden mulighed for at vide, hvor den forrige knude er. Til sammenligning ville en enkelt linket liste skulle krydse hele listen igen til det punkt, der er forud for den, for at komme til det samme punkt.

For information om enkeltstående linkede lister, se min klassekammerats artikel:

Som tidligere nævnt peger noder på andre placeringer i hukommelsen. Hvad betyder det? I modsætning til arrays, der er gemt på sammenhængende placeringer, har linkede lister simpelthen pegepunkter. I diagrammet nedenfor har hver hukommelsesblok (rød) to pointere, der peger på den. Den får adgang til disse oplysninger ved at se til næste markør (sort). Hvis den vil finde den blok, der er forud for den, vil den se på den foregående markør (hvid).

Så hvordan implementerer man en dobbeltkædet liste? Her er hvordan i Python 3

Bare tilføj en .prev til din Node-klasse. Nu er du klar til at begynde at implementere!

Fordele - Med Python 3-kode!

Hvad er nogle af fordelene ved en dobbeltkædet liste i forhold til en enkeltstående link? Nå, med en dobbelt sammenkoblet liste kan du bevæge dig baglæns og fremad mellem dine knudepunkter. Dette gør ting som at indsætte virkelig let. Med dobbeltkædede lister vil du bare krydse din linkede liste til den node, du ønsker, og derefter ringe til den forrige knude.

Ulemper

Selvom der er gode ting ved sammenkoblede lister, er det ikke en løsning, der skal være alt sammen. Som med mange datastrukturer og algoritmer bør dette være et værktøj i dit arsenal. En af ulemperne ved en enkelt linket liste er, at der er mere hukommelsesforbrug, da hvert link på en dobbeltkædet liste skal holde styr på den foregående pointer. Derudover er det vanskeligt at holde styr på nævnte markør.

Jeg er faktisk stadig i færd med at øve implementeringen af ​​dem. Dette vil have været min anden succesrige implementering fra skrivningen af ​​denne artikel (april 2019). Hver gang bliver lidt lettere, men jeg har stadig brug for at tegne diagrammer over, hvordan den forrige markør interagerer med alle mine andre funktioner.

Men hvad ville dette bruges til?

Jeg hører dig spørge. Tænk på ethvert tidspunkt, du har set et forrige og det næste. Der er nogle åbenlyse og subtile måder, de kan implementeres på.

Kilde: https://pbs.twimg.com/media/DxzXvUKXgAAvmxx.jpg

Hvad med i en sag som en musikafspiller? Det har en meget eksplicit næste og forrige knap. En dobbeltkædet liste kunne bruges til at skifte mellem disse to sange.

Eller hvad med en browser? Disse har også eksplicit måder at gå baglæns og fremad mellem de websider, du har besøgt.

Tænk nu over dit valg af tekstbehandlingssoftware eller fotoeditor. Hver gang du begår en fejl, er du i stand til at trykke på CTRL (CMD til Mac) + Z for at fortryde den sidste handling. Ligeledes er du i stand til at gøre om, hvad du har fortrydt med CTRL (CMD til Mac) + Y. Hvorfor lyder dette velkendt? Det kunne også implementeres med en dobbelt sammenkoblet liste! Den forrige markør peger på handlinger, der blev udført, samtidig med at de også kan gentage handlingerne, hvis du fortryder for meget.

Kilde: https://gfycat.com/brilliantbeautifuldassieKilde: https://www.solitairecardgames.com/how-to-play-solitaire

En mindre indlysende implementering jeg tænkte på var i spillet Solitaire. Til siden er et billede af kabale-terminologier til at illustrere mit pointe.

Spillet er et lysende eksempel, hvor du konstant har brug for at være i stand til at se de forrige og næste kort, hvad enten det er i tablå eller affaldshøjde. Når du spiller et kort fra affaldsstablen til tablået, opdateres affaldshøjlen med kortet dertil.

For en mere livlig diskussion af anvendelser på dobbelt forbundne lister vil jeg anbefale at se på denne diskussion om stackoverflow:

Så næste gang du implementerer en linket liste, hvorfor ikke prøve en dobbeltkoblet liste? Det er ikke så meget mere kode øverst på en linket liste, og der er store fordele!

Yderligere ressourcer

Et fuldt link til min Python 3-implementering af en dobbeltkædet liste kan findes på min Github-repo.

Hvis du gerne vil have en 3D-printbar kæde med dobbelt forbundne lister, har jeg uploadet den til 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