Rozdiel Medzi Zoznamom, Ktorý Je Jednotlivo Prepojený A Zoznamom S Dvojitým Prepojením

2024 Autor: Mildred Bawerman | [email protected]. Naposledy zmenené: 2023-12-16 08:42

Zoznam so samostatným odkazom vs Zoznam s dvojnásobným prepojením

Prepojený zoznam je lineárna dátová štruktúra, ktorá sa používa na ukladanie zbierky údajov. Prepojený zoznam alokuje pamäť svojim prvkom osobitne vo svojom vlastnom bloku pamäte a celková štruktúra sa získa spojením týchto prvkov ako odkazov v reťazci. Samostatne prepojený zoznam je tvorený postupnosťou uzlov a každý uzol má odkaz na nasledujúci uzol v poradí. Dvojnásobne prepojený zoznam obsahuje sekvenciu uzlov, v ktorých každý uzol obsahuje odkaz na nasledujúci uzol aj na predchádzajúci uzol.

Zoznam so samostatným odkazom

Každý prvok v jednotlivo prepojenom zozname má dve polia, ako je to znázornené na obrázku 1. V dátovom poli sú uložené skutočné údaje a ďalšie pole obsahuje odkaz na nasledujúci prvok v reťazci. Prvý prvok prepojeného zoznamu je uložený ako hlava 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 uchovávajú odkaz na nasledujúci prvok. Posledný prvok obsahuje vo svojom nasledujúcom poli nulovú hodnotu. K ľubovoľným prvkom v zozname je možné pristupovať tak, že začnete od začiatku a po nasledujúcom ukazovateli, kým nesplníte požadovaný prvok.

Dvojnásobne prepojený zoznam

Každý prvok v zozname, ktorý je dvojnásobne prepojený, má tri polia, ako je to znázornené na obrázku 3. Podobne ako v prípade samostatne prepojeného zoznamu, dátové pole obsahuje skutočne uložené údaje a ďalšie pole obsahuje odkaz na ďalší prvok v reťazci. Predchádzajúce pole navyše obsahuje odkaz na predchádzajúci prvok v reťazci. Prvý prvok prepojeného zoznamu je uložený ako hlava prepojeného zoznamu.

Obrázok 4 zobrazuje dvojnásobne prepojený zoznam s tromi prvkami. Všetky prostredné prvky ukladajú odkazy na prvý a predchádzajúci prvok. Posledný prvok v zozname obsahuje nulovú hodnotu vo svojom nasledujúcom poli a prvý prvok v zozname obsahuje nulovú hodnotu vo svojom predchádzajúcom poli. Dvojnásobne prepojeným zoznamom je možné prechádzať dopredu sledovaním ďalších odkazov v každom prvku a podobne sa dá prechádzať dozadu pomocou predchádzajúcich odkazov v každom prvku.

Aký je rozdiel medzi zoznamom Singly Linked List a Doubly Linked List?

Každý prvok v jednotlivo prepojenom zozname obsahuje odkaz na nasledujúci prvok v zozname, zatiaľ čo každý prvok v dvojnásobne prepojenom zozname obsahuje odkazy na nasledujúci prvok ako aj na predchádzajúci prvok v zozname. Dvojnásobne spojené zoznamy vyžadujú viac miesta pre každý prvok v zozname a elementárne operácie, ako je vkladanie a mazanie, sú zložitejšie, pretože musia narábať s dvoma odkazmi. Zoznamy odkazov však dvojnásobne umožňujú ľahšiu manipuláciu, pretože umožňujú prechádzanie zoznamu vpred a vzad.