Liste dublate legate și cum să le implementăm în Python 3

Listele legate sunt un mod liniar de stocare a datelor. Este format din noduri care conțin date, precum și indicatoare cu modul de a trece la următoarea bucată de date. Gândiți-vă la noduri ca membru al unui lanț. Fiecare lanț depinde unul de celălalt pentru a păstra o legătură puternică. Dacă, de exemplu, link-ul din mijloc lipsește totul după ce eșuează. Nu mai este un lanț complet! Cum se traduce asta în liste legate? Dacă unul dintre indicatoare lipsește sau este incorect, restul datelor nu mai pot fi citite.

Nu este un lanț valid! Aceasta ar rupe o listă legată!

Cu toate acestea, subiectul acestui articol este pe o versiune mai versatilă a listelor legate - lista dublu legată. În comparație cu o listă regulată (sau individuală), o listă dublă legată include un alt indicator numit anterior. După cum puteți ghici, acest lucru permite nodului să știe unde se află nodul anterior. În comparație, o listă legată individual ar trebui să traverseze din nou întreaga listă până la punctul precedent pentru a ajunge la același punct.

Pentru informații despre listele cu linkuri simple, vă rugăm să vizitați articolul colegului meu de clasă:

După cum am menționat anterior, nodurile indică alte locații din memorie. Ce inseamna asta? Ei bine, spre deosebire de tablele care sunt stocate în locații contigue, listele legate au doar indicatoare. În diagrama de mai jos fiecare bloc de memorie (roșu) are doi indicatori care îndreaptă spre el. Acesta accesează aceste informații căutând indicatorul Next (negru). Dacă dorește să găsească blocul anterior, se va uita la indicatorul anterior (alb).

Deci, cum se implementează o listă dublă legată? Uite așa în Python 3

Pur și simplu adăugați un .prev la clasa dvs. de nod. Acum sunteți gata să începeți să implementați!

Avantaje - Cu codul Python 3!

Care sunt unele dintre avantajele unei liste dublu legate față de una singură legată? Ei bine, cu o listă dublă legată, puteți să vă deplasați înapoi și înapoi între noduri. Acest lucru face ca lucrurile precum introducerea să fie foarte ușoare. Cu liste dublu legate, nu trebuie decât să traversați lista legată către nodul dorit și apoi să apelați la nodul anterior.

Dezavantaje

Deși există lucruri grozave despre listele legate, aceasta nu este o soluție completă. La fel ca în multe structuri de date și algoritmi, acesta ar trebui să fie un instrument în arsenalul dvs. Unul dintre dezavantajele unei liste cu linkuri simple este faptul că există un consum de memorie mai mare, deoarece fiecare legătură dintr-o listă dublă legată trebuie să țină evidența acelui indicator anterior. În plus, este dificil să urmărești indicatorul menționat.

Sunt încă în proces de implementare a acestora. Aceasta va fi cea de-a doua mea implementare de succes de la redactarea acestui articol (aprilie 2019). De fiecare dată devine ușor mai ușor, dar totuși trebuie să desenez diagrame despre modul în care indicatorul anterior interacționează cu toate celelalte funcții.

Dar la ce ar fi folosit acest lucru?

Am auzit că întrebi. Gândiți-vă la orice dată când ați văzut un aspect anterior și următor. Există câteva modalități evidente și subtile prin care pot fi puse în aplicare.

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

Dar într-un caz ca un player muzical? Are un buton foarte explicit următor și anterior. O listă dublu legată ar putea fi folosită pentru a face ciclul între cele două melodii.

Sau despre un browser? Acestea au, de asemenea, modalități explicite de a merge înapoi și înapoi între paginile web pe care le-ați vizitat.

Acum gândiți-vă la software-ul dvs. de procesare a textului sau la editorul de fotografii ales. De fiecare dată când faceți o greșeală, puteți apăsa CTRL (CMD pentru Mac) + Z pentru a anula ultima acțiune. De asemenea, puteți reface ceea ce ați anulat cu CTRL (CMD pentru Mac) + Y. Acum, de ce sună familiar? Poate fi implementat și cu o listă dublă legată! Indicatorul precedent indică acțiunile care au fost făcute în timp ce, de asemenea, puteți refaca acțiunile dacă anulați prea mult.

Sursa: https://gfycat.com/brilliantbeautifuldassieSursa: https://www.solitairecardgames.com/how-to-play-solitaire

O implementare mai puțin evidentă la care m-am gândit a fost în jocul Solitaire. În lateral este o imagine a terminologiilor Solitaire pentru a ajuta la ilustrarea punctului meu.

Jocul este un exemplu strălucitor în care trebuie să poți vizualiza cărțile anterioare și următoare, indiferent dacă acestea se află în tabel sau la gunoi. Pe măsură ce jucați o carte de la coșul de gunoi până la masă, grămada de deșeuri este actualizată cu cartea anterioară.

Pentru o discuție mai activă a utilizărilor pe listele dublu legate, aș recomanda să aruncați o privire la această discuție pe stackoverflow:

Așadar, data viitoare când implementați o listă legată, de ce să nu încercați una dublă legată? Nu este chiar atât de mult cod în partea de sus a unei liste legate și există beneficii profunde!

Resurse aditionale

Pe link-ul meu Github puteți găsi o legătură completă la implementarea mea Python 3 a unei liste dublu legate.

Dacă doriți un lanț imprimabil 3d de liste dublu legate, l-am încărcat pe 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