Dvostruko povezani popisi i kako ih implementirati u Python 3

Povezani popisi linearni su način pohrane podataka. Sastoji se od čvorova koji sadrže podatke kao i pokazivača kako doći do sljedećeg podatka. Razmislite o čvorovima kao o članu lanca. Svaki lanac ovisi jedan o drugom kako bi zadržao snažnu vezu. Ako, primjerice, srednjoj vezi nedostaje sve što nakon toga ne uspije. Više nije cijeli lanac! Kako se to prevodi na povezane popise? Ako jedan od pokazatelja nedostaje ili je netočan, ostatak podataka se više ne može očitati.

Nije valjan lanac! Time bi se prekinuo povezani popis!

Međutim, tema ovog članka nalazi se na svestranijoj verziji povezanih popisa - na dvostruko povezanom popisu. U usporedbi s redovitim (ili pojedinačno) povezanim popisom, dvostruko povezani popis uključuje još jedan pointer nazvan prethodni. Kao što možda pogađate, ovo čvoru omogućuje da zna gdje je prethodni čvor. Za usporedbu, pojedinačno povezani popis morao bi ponovno preći cijeli popis do točke koja je prethodila da bi došao do iste točke.

Za informacije o pojedinačno povezanim popisima posjetite članak mog razrednika:

Kao što je ranije spomenuto, čvorovi upućuju na druga mjesta u memoriji. Što to znači? Pa, za razliku od nizova koji se pohranjuju na neprekidne lokacije, povezani popisi jednostavno imaju pokazivače. U dijagramu ispod svakog bloka memorije (crvena) postoje dva pokazivača koja ga upućuju. Te informacije pristupaju gledajući sljedeći pokazivač (crno). Ako želi pronaći blok prije njega, pogledat će Prethodni pokazivač (bijeli).

Pa kako implementirati dvostruko povezan popis? Evo kako u Pythonu 3

Jednostavno dodajte .prev u vašu klasu čvorova. Sad ste spremni za početak implementacije!

Prednosti - s Python 3 kodom!

Koje su neke od prednosti dvostruko povezanih lista u odnosu na pojedinačno povezani? Pa, s dvostruko povezanim popisom, možete se kretati naprijed i naprijed između svojih čvorova. To olakšava stvari poput umetanja. S dvostruko povezanim popisima jednostavno biste prešli povezani popis do željenog čvora i pozvali prethodni čvor.

Nedostaci

Iako postoje sjajne stvari o povezanim popisima, to nije sve u svemu rješenje. Kao i kod mnogih podataka i algoritama, ovo bi trebao biti alat u vašem arsenalu. Jedan od nedostataka pojedinačno povezanog popisa je taj da postoji veća potrošnja memorije jer svaka veza s dvostruko povezanim popisom mora pratiti taj prethodni pointer. Pored toga, teško je pratiti navedeni pokazivač.

Ja se zapravo još uvijek bavim njihovom primjenom. Ovo će mi biti druga uspješna primjena od pisanja ovog članka (travanj 2019.). Svaki put mi postaje lakše, ali još uvijek moram crtati dijagrame kako prethodni pokazivač djeluje na sve moje ostale funkcije.

Ali za što bi se ovo koristilo?

Čujem da pitaš. Razmislite o svakom trenutku kad ste vidjeli prethodno i sljedeće. Postoje neki očiti i suptilni načini na koje se mogu provesti.

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

Što je sa slučajem poput glazbenog playera? Ima vrlo eksplicitni sljedeći i prethodni gumb. Dvostruko povezan popis mogao bi se koristiti za pomicanje između te dvije pjesme.

Ili što je s preglednikom? Oni također imaju izričite načine naprijed i naprijed između web stranica koje ste posjetili.

Sada razmislite o svom softveru za obradu teksta ili uređivaču fotografija po izboru. Svaki put kad pogriješite, možete poništiti CTRL (CMD za Mac) + Z da biste poništili zadnju radnju. Isto tako, možete ponoviti ono što ste poništili pomoću CTRL (CMD za Mac) + Y. Zašto sada ovo zvuči poznato? Također se može implementirati s dvostruko povezanim popisom! Prethodni pokazivač ukazuje na radnje koje su učinjene, dok je također u mogućnosti ponoviti radnje ako previše poništite.

Izvor: https://gfycat.com/brilliantbeautifuldassieIzvor: https://www.solitairecardgames.com/how-to-play-solitaire

Manje očigledna implementacija o kojoj sam razmišljao bila je u igri Pasijans. Sa strane je slika terminologija pasijansa kako bi se ilustrirao moj stav.

Igra je sjajan primjer gdje morate stalno moći pregledati prethodne i sljedeće kartice bilo da se radi o stolu ili na hrpi otpada. Dok igrate kartu s hrpom otpada na stol, otpad se ažurira s karticom koja je bila prethodna.

Za živahniju raspravu o korištenjima na dvostruko povezanim popisima, preporučam da pogledate ovu raspravu o stackoverflowu:

Dakle, sljedeći put kada implementirate povezan popis zašto ne isprobati dvostruko povezani? Nije to puno više koda na vrhu povezanog popisa i postoje velike prednosti!

Dodatni resursi

Potpuna veza na moju Python 3 implementaciju dvostruko povezanog popisa nalazi se na mom Github repo-u.

Ako želite 3D lanac za ispis s dvostruko povezanim popisima, prenio sam ga u 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