Polia vs prepojené zoznamy
Polia sú najčastejšie používanou dátovou štruktúrou na ukladanie kolekcie prvkov. Väčšina programovacích jazykov poskytuje metódy na jednoduché deklarovanie polí a prístup k prvkom v poliach. Prepojený zoznam, presnejšie single-linked list, je tiež dátová štruktúra, ktorú možno použiť na uloženie kolekcie prvkov. Pozostáva zo sekvencie uzlov a každý uzol má odkaz na nasledujúci uzol v sekvencii.
Na obrázku 1 je znázornený kus kódu, ktorý sa zvyčajne používa na deklarovanie a priraďovanie hodnôt do poľa. Obrázok 2 znázorňuje, ako by pole vyzeralo v pamäti.
Vyššie uvedený kód definuje pole, ktoré môže uložiť 5 celých čísel a pristupuje sa k nim pomocou indexov 0 až 4. Jednou z dôležitých vlastností poľa je, že celé pole je alokované ako jeden blok pamäte a každý prvok dostane 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, museli by ste definovať dostatočne veľké pole, aby ste boli na bezpečnej strane. Väčšinu času však v skutočnosti použijeme menší počet prvkov, ako sme pridelili. Značné množstvo pamäte je teda skutočne premrhané. Na druhej strane, ak „dosť veľké pole“nie je v skutočnosti dostatočne veľké, program spadne.
Prepojený zoznam prideľuje pamäť svojim prvkom oddelene vo svojom vlastnom bloku pamäte a celková štruktúra sa získa spojením týchto prvkov ako článkov v reťazci. Každý prvok v prepojenom zozname má dve polia, ako je znázornené na obrázku 3. 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.
| data | ďalší |
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 má vo svojom ďalšom poli nulovú hodnotu. K akémukoľvek prvku v zozname je možné pristupovať tak, že začnete od začiatku a budete nasledovať nasledujúci ukazovateľ, kým nesplníte požadovaný prvok.
Aj keď sú polia a prepojené zoznamy podobné v tom zmysle, že sa oba používajú na ukladanie kolekcie prvkov, vznikajú rozdiely v dôsledku stratégií, ktoré používajú na prideľovanie pamäte svojim 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 spôsobilo, že polia by boli neefektívne v situáciách, keď nepoznáte veľkosť poľa v čase kompilácie. Keďže prepojený zoznam prideľuje pamäť svojim prvkom oddelene, bolo by to veľmi efektívne 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 tým, ako priamo pristupujete k prvkom v poli pomocou jeho indexov.
