Jednoducho prepojený zoznam verzus dvojito prepojený zoznam
Prepojený zoznam je lineárna dátová štruktúra, ktorá sa používa na uloženie kolekcie dát. Prepojený zoznam prideľuje pamäť svojim prvkom oddelene vo svojom vlastnom bloku pamäte a celková štruktúra sa získa prepojením týchto prvkov ako článkov v reťazci. Jednotlivo prepojený zoznam sa skladá zo sekvencie uzlov a každý uzol má odkaz na nasledujúci uzol v sekvencii. Dvojito prepojený zoznam obsahuje sekvenciu uzlov, v ktorých každý uzol obsahuje odkaz na nasledujúci uzol, ako aj na predchádzajúci uzol.
Singly Linked List
Každý prvok v jednotlivo prepojenom zozname má dve polia, ako je znázornené na obrázku 1. Dátové pole obsahuje aktuálne uložené údaje a ďalšie pole obsahuje odkaz na ďalší prvok v reťazci. Prvý prvok prepojeného zoznamu je uložený ako hlavička prepojeného zoznamu.
Obrázok 2 zobrazuje jednotlivo prepojený zoznam s tromi prvkami. Každý prvok ukladá svoje údaje a všetky prvky okrem posledného ukladajú odkaz na nasledujúci prvok. Posledný prvok má vo svojom ďalšom poli nulovú hodnotu. K akémukoľvek prvku v zozname môžete pristupovať tak, že začnete od začiatku a budete nasledovať nasledujúci ukazovateľ, kým nesplníte požadovaný prvok.
Zoznam s dvojitým odkazom
Každý prvok v dvojito prepojenom zozname má tri polia, ako je znázornené na obrázku 3. Podobne ako pri jednoducho prepojenom zozname, dátové pole obsahuje aktuálne uložené údaje a ďalšie pole obsahuje odkaz na ďalší prvok v reťazci. Okrem toho predchádzajúce pole obsahuje odkaz na predchádzajúci prvok v reťazci. Prvý prvok prepojeného zoznamu je uložený ako hlavička prepojeného zoznamu.
Obrázok 4 zobrazuje dvojito prepojený zoznam s tromi prvkami. Všetky medziľahlé prvky ukladajú odkazy na prvý a predchádzajúci prvok. Posledný prvok v zozname má vo svojom nasledujúcom poli nulovú hodnotu a prvý prvok v zozname má v predchádzajúcom poli nulovú hodnotu. Dvojito prepojený zoznam je možné prechádzať dopredu sledovaním nasledujúcich referencií v každom prvku a podobne je možné prechádzať dozadu pomocou predchádzajúcich referencií v každom prvku.
Aký je rozdiel medzi zoznamom s jedným prepojením a zoznamom s dvojitým odkazom?
Každý prvok v jednoducho prepojenom zozname obsahuje odkaz na nasledujúci prvok v zozname, zatiaľ čo každý prvok v dvojito prepojenom zozname obsahuje odkazy na nasledujúci prvok, ako aj na predchádzajúci prvok v zozname. Dvojito prepojené zoznamy vyžadujú viac miesta pre každý prvok v zozname a základné operácie, ako je vkladanie a mazanie, sú zložitejšie, pretože musia pracovať s dvoma odkazmi. Dvojité zoznamy odkazov však umožňujú jednoduchšiu manipuláciu, pretože umožňujú prechádzať zoznamom dopredu a dozadu.
