Matrike proti povezanim seznamom
Matrike so najpogosteje uporabljena podatkovna struktura za shranjevanje zbirke elementov. Večina programskih jezikov ponuja metode za preprosto deklariranje nizov in dostop do elementov v nizih. Povezani seznam, natančneje enojno povezani seznam, je tudi podatkovna struktura, ki se lahko uporablja za shranjevanje zbirke elementov. Sestavljen je iz zaporedja vozlišč in vsako vozlišče ima referenco na naslednje vozlišče v zaporedju.
Na sliki 1 je prikazan del kode, ki se običajno uporablja za deklariranje in dodeljevanje vrednosti matriki. Slika 2 prikazuje, kako bi matrika izgledala v pomnilniku.
Zgornja koda definira matriko, ki lahko shrani 5 celih števil in do njih se dostopa z uporabo indeksov od 0 do 4. Ena od pomembnih lastnosti matrike je, da je celotna matrika dodeljena kot en blok pomnilnika in vsak element dobi svoj prostor v nizu. Ko je matrika definirana, je njena velikost fiksna. Torej, če niste prepričani o velikosti matrike v času prevajanja, bi morali definirati dovolj veliko matriko, da boste na varni strani. Toda večino časa bomo dejansko uporabili manj elementov, kot smo jih dodelili. Tako je precejšnja količina pomnilnika dejansko izgubljena. Po drugi strani pa, če »dovolj velik niz« dejansko ni dovolj velik, bi se program zrušil.
Povezani seznam dodeljuje pomnilnik svojim elementom ločeno v lastnem bloku pomnilnika, celotna struktura pa je pridobljena s povezovanjem teh elementov kot členov v verigi. Vsak element na povezanem seznamu ima dve polji, kot je prikazano na sliki 3. Podatkovno polje vsebuje dejanske shranjene podatke, naslednje polje pa sklic na naslednji element v verigi. Prvi element povezanega seznama je shranjen kot glava povezanega seznama.
| podatki | naslednji |
Slika 3: Element povezanega seznama
Slika 4 prikazuje povezan seznam s tremi elementi. Vsak element shrani svoje podatke in vsi elementi razen zadnjega shranijo referenco na naslednji element. Zadnji element ima v svojem naslednjem polju ničelno vrednost. Do katerega koli elementa na seznamu lahko dostopate tako, da začnete pri glavi in sledite naslednjemu kazalcu, dokler ne srečate zahtevanega elementa.
Čeprav so matrike in povezani seznami podobni v smislu, da se oba uporabljata za shranjevanje zbirke elementov, povzročajo razlike zaradi strategij, ki jih uporabljajo za dodeljevanje pomnilnika svojim elementom. Matrike dodelijo pomnilnik vsem svojim elementom kot enemu bloku, velikost matrike pa je treba določiti med izvajanjem. To bi naredilo nize neučinkovite v situacijah, ko v času prevajanja ne poznate velikosti niza. Ker povezani seznam dodeljuje pomnilnik svojim elementom ločeno, bi bil zelo učinkovit v situacijah, ko v času prevajanja ne poznate velikosti seznama. Deklaracija in dostop do elementov na povezanem seznamu ne bi bila enostavna v primerjavi z neposrednim dostopom do elementov v matriki z uporabo njenih indeksov.
