Zdvojeně propojené seznamy a jak je implementovat v Pythonu 3

Propojené seznamy jsou lineárním způsobem ukládání dat. Skládá se z uzlů, které obsahují data, jakož i ukazatelů, jak se dostat k dalšímu datu. Zamyslete se nad uzly jako s řetězem. Každý řetěz závisí na sobě, aby si udržel silné pouto. Pokud například střední odkaz chybí vše poté, co selže. Už to není kompletní řetěz! Jak se to překládá do propojených seznamů? Pokud jeden z ukazatelů chybí nebo je nesprávný, nelze již zbývající data číst.

Není to platný řetěz! Tím by se porušil propojený seznam!

Tématem tohoto článku je však více univerzální verze propojených seznamů - dvojitě propojený seznam. Ve srovnání s běžným (nebo samostatně) propojeným seznamem obsahuje dvojitě propojený seznam další ukazatel nazývaný předchozí. Jak asi uhodnete, umožní to uzlu zjistit, kde je předchozí uzel. Ve srovnání by jednotlivě propojený seznam musel procházet celý seznam znovu do bodu předcházejícího, aby se dostal ke stejnému bodu.

Informace o samostatně propojených seznamech naleznete v článku mého spolužáka:

Jak již bylo zmíněno, uzly ukazují na jiná místa v paměti. Co to znamená? Na rozdíl od polí uložených na sousedních místech mají propojené seznamy jednoduše ukazatele. Na obrázku pod každým blokem paměti (červený) jsou dva ukazatele, které na něj ukazují. K těmto informacím přistupuje pohledem na další ukazatel (černý). Pokud chce najít blok před ním, podívá se na předchozí ukazatel (bílý).

Jak tedy implementovat dvojitě propojený seznam? "Jak je to v Pythonu 3."

Jednoduše přidejte .prev do své třídy Node. Nyní jste připraveni začít implementovat!

Výhody - S Python 3 kódem!

Jaké jsou výhody dvojitě propojeného seznamu oproti jednotlivě propojenému seznamu? Díky dvojitě propojenému seznamu se můžete pohybovat dozadu a dopředu mezi svými uzly. Díky tomu je vkládání opravdu snadné. S dvojitě propojenými seznamy byste jednoduše procházeli propojeným seznamem do požadovaného uzlu a poté zavolali na předchozí uzel.

Nevýhody

I když jsou o propojených seznamech skvělé věci, nejedná se o všestranné řešení. Stejně jako u mnoha datových struktur a algoritmů by to měl být nástroj ve vašem arzenálu. Jednou z nevýhod oproti jednotlivě propojenému seznamu je to, že existuje větší spotřeba paměti, protože každý odkaz ve dvojitě propojeném seznamu musí sledovat předchozí ukazatel. Navíc je obtížné sledovat uvedený ukazatel.

Jsem ve skutečnosti stále v procesu jejich implementace. To bude moje druhá úspěšná implementace od psaní tohoto článku (duben 2019). Pokaždé, když je to o něco snazší, ale stále musím nakreslit schémata interakce předchozího ukazatele se všemi mými ostatními funkcemi.

Ale k čemu by to bylo použito?

Slyšel jsem, že se ptáš. Přemýšlejte o tom, kdykoli jste viděli předchozí a další. Existuje několik zřejmých a jemných způsobů, jak je lze implementovat.

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

A co v případě jako hudební přehrávač? Má velmi explicitní další a předchozí tlačítko. Mezi těmito dvěma písněmi lze cyklicky propojovat seznam.

Nebo co prohlížeč? Jsou zde také explicitní způsoby, jak se pohybovat mezi webovými stránkami, které jste navštívili, dozadu a dopředu.

Nyní přemýšlejte o svém softwaru pro zpracování textu nebo editoru fotografií. Kdykoli uděláte chybu, můžete stiskem kláves CTRL (CMD pro Mac) + Z zrušit poslední akci. Stejně tak můžete opakovat to, co jste zrušili, pomocí CTRL (CMD pro Mac) + Y. Proč to tedy zní dobře? Mohlo by být také implementováno s dvojitě propojeným seznamem! Předchozí ukazatel ukazuje na akce, které byly provedeny, a je také schopen akce opakovat, pokud zrušíte příliš mnoho.

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

Méně zřejmá implementace, o které jsem si myslel, byla ve hře Solitaire. Na straně je obrázek Solitaire terminologií, které pomáhají ilustrovat můj názor.

Hra je zářným příkladem, kde musíte neustále prohlížet předchozí a další karty, ať už jsou na stole nebo na hromádce odpadu. Když hrajete kartu z hromady odpadu na tablo, hromada odpadu se aktualizuje s kartou před ní.

Pro živější diskusi o použití na dvojitě propojených seznamech bych doporučil podívat se na tuto diskusi o stackoverflow:

Takže až příště implementujete propojený seznam, proč nezkusit dvojitě propojený seznam? Nejedná se o tolik kódů navíc na propojený seznam a existují hluboké výhody!

Dodatečné zdroje

Úplný odkaz na implementaci dvojitě propojeného seznamu v mém Pythonu 3 najdete na mém repozitáři Github.

Pokud byste chtěli 3d tisknutelný řetězec dvojitě propojených seznamů, nahrál jsem jej do 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