Razlika med nizi in povezanimi seznami

Nizi in povezani seznami

Matri so najpogosteje uporabljena struktura podatkov za shranjevanje zbirke elementov. Večina programskih jezikov ponuja metode za enostavno deklariranje nizov in dostop do elementov v matrikah. Povezani seznam, natančneje samostojno povezan seznam, je tudi struktura podatkov, 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 del kode, ki se običajno uporablja za razglasitev in dodelitev vrednosti matriki. Slika 2 prikazuje, kako bi v pomnilniku izgledal niz.

Zgornja koda določa matriko, ki lahko shrani 5 celih števil in do njih dostopajo z indeksi 0 do 4. Ena pomembna lastnost matrike je, da je celotna matrika dodeljena kot en blok pomnilnika in vsak element dobi svoj prostor v matriki. Ko je niz definiran, je njegova velikost določena. Če v času prevajanja niste prepričani o velikosti matrike, bi morali definirati dovolj velik niz, da bo na varni strani. Toda večino časa bomo dejansko uporabili manjše število elementov, kot smo jih dodelili. Tako je zapravila precejšnjo količino spomina. Po drugi strani pa, če "dovolj velik niz" dejansko ni dovolj velik, bi se program zrušil.

Povezani seznam dodeli spomin svojim elementom ločeno v svojem bloku pomnilnika, celotna struktura pa je pridobljena 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 dejanske shranjene podatke in naslednje polje vsebuje 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 in vse elemente, razen zadnjega shrani referenco na naslednji element. Zadnji element ima ničelno vrednost v naslednjem polju. Do katerega koli elementa na seznamu lahko dostopate tako, da začnete na čelu in sledite naslednjem kazalcu, dokler ne izpolnite želenega elementa.

Čeprav so matrike in povezani seznami podobni v smislu, da se oba uporabljata za shranjevanje zbirke elementov, imata razlike zaradi strategij, ki jih uporabljata za dodelitev pomnilnika njenim elementom. Niz razporedi spomin na vse njegove elemente kot en sam blok, velikost matrike pa mora biti določena med izvajanjem. Zaradi tega bodo matrike neučinkovite v okoliščinah, ko velikosti matrike ne poznate v času prevajanja. Ker povezan seznam dodeli pomnilnik svojim elementom ločeno, bi bil zelo učinkovit v situacijah, v katerih ne poznate velikosti seznama v času prevajanja. Izjava in dostop do elementov na povezanem seznamu ne bi bila naravnost naprej v primerjavi z načinom neposrednega dostopa do elementov v matriki z uporabo njegovih indeksov.