Dvigubai susieti sąrašai ir kaip juos įgyvendinti „Python 3“

Susieti sąrašai yra linijinis duomenų saugojimo būdas. Jį sudaro mazgai, kuriuose yra duomenų, taip pat patarimai, kaip patekti į kitą duomenų dalį. Pagalvokite apie mazgus kaip grandinės narį. Kiekviena grandinė priklauso nuo kitos, kad išlaikytų tvirtą ryšį. Pavyzdžiui, jei trūksta vidurinės grandies, visko trūksta. Tai nebėra visa grandinė! Kaip tai verčiama į susietus sąrašus? Jei trūksta vieno iš rodyklių arba jis neteisingas, likusių duomenų nebegalima nuskaityti.

Netinkama grandinė! Tai sulaužytų susietą sąrašą!

Tačiau šio straipsnio tema yra labiau universali susietų sąrašų versija - dvigubai susietų sąrašų. Palyginus su įprastu (arba atskirai) susietu sąrašu, dvigubai susietas sąrašas apima kitą rodyklę, vadinamą ankstesne. Kaip jau galima spėti, tai leidžia mazgui žinoti, kur yra ankstesnis mazgas. Palyginimui, atskirai susietas sąrašas turėtų perbraukti visą sąrašą iki taško, kuris buvo ankstesnis, kad patektų į tą patį tašką.

Norėdami rasti informacijos apie atskirai susietus sąrašus, skaitykite mano klasės draugo straipsnį:

Kaip minėta anksčiau, mazgai nurodo kitas atminties vietas. Ką tai reiškia? Na, skirtingai nuo masyvų, kurie saugomi gretimose vietose, susieti sąrašai tiesiog turi rodykles. Žemiau esančioje diagramoje kiekvienas atminties blokas (raudonas) turi du rodykles, nukreipiančius į jį. Prie šios informacijos jis gali patekti žiūrėdamas į rodyklę Kitas (juodas). Jei jis nori rasti ankstesnį bloką, jis pažiūrės į ankstesnį žymeklį (baltas).

Taigi, kaip įgyvendinti dvigubai susietą sąrašą? „Štai kaip„ Python 3 “

Tiesiog pridėkite .prev prie savo „Node“ klasės. Dabar esate pasiruošę pradėti įgyvendinti!

Privalumai With - Su „Python 3“ kodu!

Kokie yra dvigubai susieto sąrašo pranašumai, palyginti su atskirai susietu sąrašu? Na, turėdami dvigubai susietą sąrašą, galite judėti pirmyn ir atgal tarp savo mazgų. Tai padaro tokius dalykus kaip įterpimas tikrai lengvus. Esant dvigubai susietiems sąrašams, jūs tiesiog perkelsite susietą sąrašą į norimą mazgą ir tada paskambinsite į ankstesnį mazgą.

Trūkumai

Nors yra daug dalykų, susijusių su susietais sąrašais, tai nėra sprendimas visiems. Kaip ir daugelio duomenų struktūrų bei algoritmų atveju, tai turėtų būti jūsų arsenalo įrankis. Vienas iš trūkumų, palyginti su atskirai susietu sąrašu, yra tas, kad sunaudojama daugiau atminties, nes kiekviena dvigubai susieto sąrašo nuoroda turi sekti ankstesnį rodyklę. Be to, sunku sekti minėtą rodyklę.

Aš iš tikrųjų vis dar praktikuoju jų įgyvendinimą. Rašant šį straipsnį (2019 m. Balandžio mėn.) Tai bus mano antrasis sėkmingas įgyvendinimas. Kiekvieną kartą pasidaro šiek tiek lengviau, bet man vis tiek reikia nupiešti schemas, kaip ankstesnis rodyklė sąveikauja su visomis kitomis mano funkcijomis.

Bet kam tai būtų naudojama?

Girdžiu jus klausiant. Pagalvokite apie bet kurį laiką, kai matėte ankstesnį ir kitą. Yra keletas akivaizdžių ir subtilių būdų, kaip juos įgyvendinti.

Šaltinis: https://pbs.twimg.com/media/DxzXvUKXgAAvmxx.jpg

O kaip tokiu atveju kaip muzikos grotuvas? Jis turi labai aiškų kitą ir ankstesnį mygtuką. Dvigubai susietas sąrašas galėtų būti naudojamas perjungti tarp šių dviejų dainų.

Arba naršyklė? Jie taip pat turi aiškius būdus, kaip grįžti į priekį ir atgal iš tinklalapių, kuriuose lankėtės.

Dabar pagalvokite apie pasirinktą teksto apdorojimo programinę įrangą ar nuotraukų redaktorių. Kiekvieną kartą padarius klaidą, galite paspausti CTRL (CMD, skirtą „Mac“) + Z, kad anuliuotumėte paskutinį veiksmą. Panašiai jūs galite perdaryti tai, ko nepadarėte naudodami CTRL (CMD, skirtą „Mac“) + Y. Kodėl dabar tai skamba pažįstamai? Tai taip pat galėtų būti įgyvendintas naudojant dvigubai susietą sąrašą! Ankstesnis rodyklė nurodo veiksmus, kurie buvo atlikti, ir kartu galėjo perdaryti veiksmus, jei per daug atšauksi.

Šaltinis: https://gfycat.com/brilliantbeautifuldassieŠaltinis: https://www.solitairecardgames.com/how-to-play-solitaire

Mažiau akivaizdus įgyvendinimas, apie kurį galvojau, buvo žaidime „Solitaire“. Į šoną yra pasjanso terminijos vaizdas, kuris padės paaiškinti mano mintį.

Žaidimas yra puikus pavyzdys, kai reikia nuolat žiūrėti ankstesnes ir kitas kortas, nesvarbu, ar tai būtų lentelėje, ar atliekų krūva. Kai žaidžiate kortele nuo atliekų krūvos iki stalo, šiukšlių krūva atnaujinama kartu su ankstesne kortele.

Jei norite gyvesnės diskusijos apie dvigubai susietų sąrašų naudojimą, aš rekomenduočiau pažvelgti į šią diskusiją apie „stackoverflow“:

Taigi, kai kitą kartą įdiegsite susietą sąrašą, kodėl gi neišbandžius dvigubai susieto sąrašo? Tai nėra daug daugiau kodo, susieto sąrašo viršuje, ir tai yra didžiulė nauda!

Papildomi resursai

Visą nuorodą į mano „Python 3“ dvigubai susieto sąrašo įgyvendinimą galite rasti mano „Github“ repo.

Jei norėtumėte 3D spausdinimo dvigubai susietų sąrašų grandinės, įkėliau ją į „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