Pochybne prepojené zoznamy a ich implementácia v Pythone 3

Prepojené zoznamy sú lineárnym spôsobom ukladania údajov. Pozostáva z uzlov, ktoré obsahujú údaje, ako aj ukazovateľov, ako sa dostať k ďalšej časti údajov. Premýšľajte o uzloch ako o členovi reťazca. Každý reťazec závisí od seba navzájom, aby si udržal silné puto. Ak napríklad strednému odkazu chýba všetko potom, čo zlyhá. Už to nie je úplný reťaz! Ako sa to prekladá do prepojených zoznamov? Ak jeden z ukazovateľov chýba alebo je nesprávny, zvyšné údaje už nie je možné prečítať.

Nie je platný reťazec! Tým by sa porušil prepojený zoznam!

Témou tohto článku je však viac univerzálna verzia prepojených zoznamov - dvojnásobne prepojený zoznam. V porovnaní s bežným (alebo jednotlivo) prepojeným zoznamom obsahuje dvojnásobne prepojený zoznam ďalší ukazovateľ nazývaný predchádzajúci. Ako asi viete, umožňuje to uzlu zistiť, kde sa nachádza predchádzajúci uzol. Na porovnanie, jednotlivo prepojený zoznam by musel prejsť celým zoznamom znova do bodu predchádzajúceho, aby sa dostal k rovnakému bodu.

Informácie o zoznamoch, ktoré sú vzájomne prepojené, nájdete v článku môjho spolužiaka:

Ako už bolo spomenuté, uzly smerujú na iné miesta v pamäti. Čo to znamená? Na rozdiel od polí, ktoré sú uložené na priľahlých miestach, prepojené zoznamy jednoducho obsahujú ukazovatele. Na obrázku pod každým blokom pamäte (červený) sú dva ukazovatele, ktoré naň odkazujú. K týmto informáciám pristupuje pohľadom na ukazovateľ Ďalší (čierny). Ak chce nájsť blok predchádzajúci, zobrazí sa ukazovateľ Predchádzajúci (biely).

Ako teda môžeme implementovať dvojnásobne prepojený zoznam? „Ako je to v Pythone 3?

Jednoducho pridajte .prev do svojej triedy Node. Teraz ste pripravení začať implementovať!

Výhody - S kódom Python 3!

Aké sú výhody dvojnásobne prepojeného zoznamu oproti jednotlivo prepojenému zoznamu? S dvojnásobne prepojeným zoznamom sa môžete pohybovať dozadu a dopredu medzi svojimi uzlami. Vďaka tomu je vkladanie skutočne jednoduché. Pri dvojnásobne prepojených zoznamoch by ste jednoducho prešli prepojeným zoznamom do požadovaného uzla a potom zavolali na predchádzajúci uzol.

Nevýhody

Hoci sú prepojené zoznamy skvelé, nie je to všestranné riešenie. Rovnako ako u mnohých dátových štruktúr a algoritmov by to mal byť nástroj vo vašom arzenáli. Jednou z nevýhod oproti zoznamom, ktoré sú samostatne prepojené, je to, že existuje väčšia spotreba pamäte, pretože každý odkaz v dvakrát prepojenom zozname musí sledovať predchádzajúci ukazovateľ. Okrem toho je ťažké sledovať uvedený ukazovateľ.

Vlastne som stále v procese ich vykonávania. Toto bude moja druhá úspešná implementácia v čase písania tohto článku (apríl 2019). Zakaždým sa to trochu uľahčí, ale stále musím nakresliť diagramy toho, ako predchádzajúci ukazovateľ interaguje so všetkými ostatnými funkciami.

Na čo by sa to však použilo?

Počul som, že sa pýtaš. Zamyslite sa nad tým, kedy ste videli predchádzajúce a nasledujúce. Existuje niekoľko zrejmých a jemných spôsobov, ako ich možno realizovať.

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

A čo v prípade ako hudobný prehrávač? Má veľmi explicitné nasledujúce a predchádzajúce tlačidlo. Na prepínanie medzi týmito dvoma skladbami by sa mohol použiť dvojnásobne prepojený zoznam.

Alebo čo prehliadač? Majú tiež explicitné spôsoby, ako sa pohybovať dozadu a dopredu medzi webovými stránkami, ktoré ste navštívili.

Teraz premýšľajte o svojom softvéri na spracovanie textu alebo výbere editora fotografií. Vždy, keď urobíte chybu, môžete stlačiť CTRL (CMD pre Mac) + Z a vrátiť sa k poslednej akcii. Podobne dokážete opakovať to, čo ste zrušili pomocou CTRL (CMD pre Mac) + Y. Prečo teraz to znie povedome? Môže byť tiež implementovaný s dvojnásobne prepojeným zoznamom! Predchádzajúci ukazovateľ ukazuje na akcie, ktoré sa vykonali, a ak je ich vrátenie príliš veľa, je možné ich tiež opakovať.

Zdroj: https://gfycat.com/brilliantbeautifuldassieZdroj: https://www.solitairecardgames.com/how-to-play-solitaire

Menej zrejmá implementácia, na ktorú som myslel, bola v hre Solitaire. Na strane je obrázok terminológií Solitaire, ktorý pomáha ilustrovať môj názor.

Hra je žiarivým príkladom, v ktorom musíte neustále pozerať predchádzajúce a nasledujúce karty, či už na stole alebo na hromade odpadu. Keď hráte kartu od hromady odpadu po tabu, hromada odpadu sa aktualizuje kartou pred ňou.

Pre živšiu diskusiu o použití v dvojito prepojených zoznamoch odporúčam pozrieť sa na túto diskusiu o kompromise:

Takže nabudúce, keď implementujete prepojený zoznam, prečo nevyskúšať dvojito prepojený zoznam? Nejde o toľko kódov navrchu prepojeného zoznamu a existujú obrovské výhody!

Dodatočné zdroje

Úplný odkaz na moju implementáciu dvojito prepojeného zoznamu v Pythone 3 nájdete na mojom repozitári Github.

Ak by ste chceli reťaz s dvojnásobne prepojenými zoznamami, ktorú je možné vytlačiť, odovzdal som ju do spoločnosti 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