Nizov vs povezanih seznamov
Polja so najpogosteje uporabljena podatkovna struktura za shranjevanje zbirke elementov. Večina programskih jezikov ponuja metode za enostavno razglasitev nizov in dostop do elementov v nizih. Povezani seznam, natančneje posamezno povezan seznam, je tudi podatkovna struktura, ki se lahko uporablja za shranjevanje zbirke elementov. Sestavljen je iz zaporedja vozlišč in vsako vozlišče ima sklic na naslednje vozlišče v zaporedju.
Na sliki 1 je prikazan del kode, ki se običajno uporablja za deklariranje in dodelitev vrednosti matriki. Slika 2 prikazuje, kako bi bila matrika videti v spominu.
Zgornja koda definira matriko, ki lahko shrani 5 celih števil, do njih pa se dostopa s pomočjo indeksov od 0 do 4. Ena pomembnih lastnosti matrike je, da je celotno polje dodeljeno kot en blok pomnilnika in vsak element dobi svoj prostor v matriki. Ko je polje definirano, je njegova velikost fiksna. Če torej niste prepričani o velikosti matrike v času prevajanja, bi morali določiti dovolj veliko matriko, da bi bila na varni strani. Toda večino časa bomo dejansko uporabili manj elementov, kot smo jih dodelili. Tako je dejansko zapravljena precejšnja količina pomnilnika. Po drugi strani pa, če »dovolj velika matrika« dejansko ni dovolj velika, bi se program zrušil.
Povezani seznam razdeli pomnilnik svojim elementom ločeno v svojem bloku pomnilnika in celotno strukturo dobimo s povezovanjem teh elementov kot povezav v verigi. Vsak element na povezanem seznamu ima dve polji, kot je prikazano na sliki 3. Podatkovno polje vsebuje dejansko shranjene podatke, naslednje polje pa sklic na naslednji element v verigi. Prvi element povezanega seznama je shranjen kot glava povezanega seznama.
Slika 3: Element povezanega seznama
Slika 4 prikazuje povezan seznam s tremi elementi. Vsak element shrani svoje podatke, vsi elementi, razen zadnjega, pa sklic na naslednji element. Zadnji element ima v naslednjem polju vrednost nič. Do katerega koli elementa na seznamu je mogoče dostopati tako, da začnete z glave in sledite naslednjemu kazalcu, dokler ne izpolnite zahtevanega elementa.
Čeprav so nizi in povezani seznami podobni v smislu, da se oba uporabljata za shranjevanje zbirke elementov, se pojavljajo razlike zaradi strategij, s katerimi se elementom dodeli spomin. Polja dodelijo pomnilnik vsem njegovim elementom kot en blok, velikost polja pa je treba določiti med izvajanjem. Zaradi tega bi bili nizi neučinkoviti v primerih, ko ne veste velikosti polja v času prevajanja. Ker povezani seznam ločeno dodeli pomnilnik svojim elementom, bi bil zelo učinkovit v situacijah, v katerih ne veste velikosti seznama v času prevajanja. Izjava in dostop do elementov na povezanem seznamu ne bi bila neposredna v primerjavi s tem, kako neposredno dostopate do elementov v polju z uporabo njenih indeksov.
