Pole vs Prepojené zoznamy
Polia sú najbežnejšie používanou dátovou štruktúrou na ukladanie kolekcie prvkov. Väčšina programovacích jazykov poskytuje metódy na ľahké deklarovanie polí a prístup k prvkom 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. Skladá sa z postupnosti uzlov a každý uzol má odkaz na nasledujúci uzol v poradí.
Na obrázku 1 je kúsok kódu, ktorý sa zvyčajne používa na deklaráciu a priradenie hodnôt k poľu. Obrázok 2 zobrazuje, ako by vyzeralo pole v pamäti.
Vyššie uvedený kód definuje pole, ktoré dokáže uložiť 5 celých čísel a je k nim prístup pomocou indexov 0 až 4. Jednou dôležitou vlastnosťou poľa je to, že celé pole je alokované ako jeden blok pamäte a každý prvok v ňom má svoj vlastný priestor. Po definovaní poľa je jeho veľkosť pevná. Takže ak si nie ste istí veľkosťou poľa v čase kompilácie, museli by ste definovať dostatočne veľké pole, aby ste boli na bezpečnej strane. Väčšinou však skutočne 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 skutočne dosť veľké, program by zlyhal.
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. Každý prvok v prepojenom zozname má dve polia, ako je to znázornené na obrázku 3. 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 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 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.
Aj keď sú polia a prepojené zoznamy podobné v tom zmysle, že sa obidva používajú na ukladanie kolekcie prvkov, vznikajú rozdiely v dôsledku stratégií, ktoré používajú na alokovanie pamäte svojim prvkom. Polia prideľujú pamäť všetkým jej prvkom ako jeden blok a veľkosť poľa sa musí určiť za behu programu. Toto 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 alokuje pamäť svojim prvkom osobitne, bolo by to oveľa efektívnejšie v situáciách, keď nepoznáte veľkosť zoznamu v čase kompilácie. Deklarácia a prístup k prvkom v prepojenom zozname by neboli priame v porovnaní s priamym prístupom k prvkom v poli pomocou jeho indexov.
