Rozdiel medzi poliami a prepojenými zoznamami

Polia vs prepojené zoznamy

Polia sú najbežnejšie používanou štruktúrou údajov na ukladanie kolekcie prvkov. Väčšina programovacích jazykov poskytuje metódy na jednoduché deklarovanie polí a prístupových prvkov v poliach. Prepojený zoznam, presnejšie jednotlivo prepojený zoznam, je tiež dátovou štruktúrou, ktorú je možné použiť na ukladanie kolekcie prvkov. Pozostáva zo sekvencie uzlov a každý uzol má odkaz na nasledujúci uzol v sekvencii.

Obrázok 1 je časť kódu, ktorá sa obvykle používa na deklarovanie a priradenie hodnôt k polu. Obrázok 2 zobrazuje, ako by pole vyzeralo v pamäti.

Vyššie uvedený kód definuje pole, do ktorého je možné uložiť 5 celých čísel a ku ktorým sa pristupuje pomocou indexov 0 až 4. Jednou z dôležitých vlastností poľa je to, že celé pole je pridelené ako jeden blok pamäte a každý prvok získa svoj vlastný priestor v poli. Akonáhle je pole definované, jeho veľkosť je pevná. Takže ak si nie ste istí veľkosťou poľa v čase kompilácie, budete musieť definovať dostatočne veľké pole, aby bolo na bezpečnej strane. Väčšinu času však v skutočnosti použijeme menší počet prvkov, ako sme pridelili. Takže značné množstvo pamäte je skutočne zbytočné. Na druhej strane, ak „dostatočne veľké pole“ nie je v skutočnosti dosť veľké, program by zlyhal.

Prepojený zoznam prideľuje 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. Každý prvok v prepojenom zozname má dve polia, ako je znázornené na obrázku 3. Dátové pole obsahuje skutočné uložené údaje a nasledujúce pole obsahuje odkaz na ďalší prvok v reťazci. Prvý prvok prepojeného zoznamu je uložený ako vedúci prepojeného zoznamu.

Obrázok 3: Prvok prepojeného zoznamu

Obrázok 4 zobrazuje 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 obsahuje vo svojom nasledujúcom poli nulovú hodnotu. Prístup k ľubovoľnému prvku v zozname je možný tak, že začnete na hlave a sledujete nasledujúci ukazovateľ, kým nedosiahnete požadovaný prvok.

Aj keď sú polia a prepojené zoznamy podobné v tom zmysle, že obidve sa používajú na ukladanie kolekcie prvkov, vznikajú rozdiely v dôsledku stratégií, ktoré používajú na pridelenie pamäte jej prvkom. Polia prideľujú pamäť všetkým svojim prvkom ako jeden blok a veľkosť poľa sa musí určiť za behu. To by urobilo polia neúčinnými v situáciách, keď nepoznáte veľkosť poľa v čase kompilácie. Pretože prepojený zoznam prideľuje pamäť jednotlivým prvkom osobitne, bolo by to oveľa efektívnejšie v situáciách, keď nepoznáte veľkosť zoznamu v čase kompilácie. Vyhlásenie a prístup k prvkom v prepojenom zozname by neboli priame v porovnaní s tým, ako priamo pristupujete k prvkom v poli pomocou jeho indexov.