Massiivid vs lingitud loendid
Massiivid on elementide kogu salvestamiseks kõige sagedamini kasutatav andmestruktuur. Enamik programmeerimiskeeli pakub meetodeid massiivide ja massiividele juurdepääsu elementide hõlpsaks deklareerimiseks. Lingitud loend, täpsemalt üksikult lingitud loend, on ka andmestruktuur, mida saab kasutada elementide kogu salvestamiseks. See koosneb sõlmede järjestusest ja igal sõlmel on viide järjestuse järgmisele sõlmele.
Joonisel 1 on kooditükk, mida tavaliselt kasutatakse massiivi väärtuste deklareerimiseks ja määramiseks. Joonisel 2 on kujutatud, kuidas massiiv mälus välja näeks.
Koodi kohal määratletakse massiiv, kuhu saab salvestada 5 täisarvu ja neile pääseb juurde indeksite 0 kuni 4 abil. Massiivi üks oluline omadus on see, et kogu massiiv eraldatakse ühe mäluplokina ja iga element saab massiivis oma ruumi. Kui massiiv on määratletud, on selle suurus fikseeritud. Nii et kui te pole kompileerimise ajal massiivi suuruses kindel, peaksite turvalise külje jaoks määrama piisavalt suure massiivi. Kuid enamasti kasutame tegelikult vähem elemente, kui oleme eraldanud. Nii et arvestatav hulk mälu läheb tegelikult raisku. Teisest küljest, kui „piisavalt suur massiiv” pole tegelikult piisavalt suur, kukuks programm kokku.
Lingitud loend eraldab mälu oma elementidele eraldi oma mäluplokis ja üldstruktuur saadakse nende elementide linkides ahelas. Igal lingitud loendi elemendil on kaks välja, nagu on näidatud joonisel 3. Andmeväli sisaldab tegelikke salvestatud andmeid ja järgmine väli sisaldab viidet ahela järgmisele elemendile. Lingitud loendi esimene element salvestatakse lingitud loendi peana.
Joonis 3: Lingitud loendi element
Joonisel 4 on kujutatud lingitud kolme elemendiga loendit. Iga element salvestab oma andmed ja kõik elemendid, välja arvatud viimane, salvestavad viite järgmisele elemendile. Viimane element omab oma järgmise välja nullväärtust. Mis tahes loendis olevale elemendile pääseb juurde, alustades peast ja järgides järgmist osutit, kuni vastate nõutavale elemendile.
Ehkki massiivid ja lingitud loendid on selles mõttes sarnased, et neid mõlemaid kasutatakse elementide kogu salvestamiseks, tekivad neil erinevused seoses strateegiatega, mida nad mälu eraldamiseks selle elementidele kasutavad. Massiivid eraldavad mälu kõigile selle elementidele ühe plokina ja massiivi suurus tuleb kindlaks määrata käitamise ajal. See muudaks massiivid ebaefektiivseks olukordades, kus te ei tea massiivi suurust kompileerimise ajal. Kuna lingitud loend eraldab mälu oma elementidele eraldi, oleks see palju tõhusam olukordades, kus te ei tea loendi suurust kompileerimise ajal. Deklareerimine ja lingitud loendis olevate elementide juurde pääsemine ei oleks otsene võrreldes sellega, kuidas massiivi elementidele otse selle indeksite abil juurde pääsete.
