Massiivide ja lingitud loendite erinevus

Massiivid vs lingitud loendid

Massiivid on elementide kogumise salvestamiseks kõige sagedamini kasutatavad andmestruktuurid. Enamik programmeerimiskeeli pakub meetodeid massiivide ja massiivides olevate elementide hõlpsaks deklareerimiseks. Lingitud loend, täpsemalt eraldi ühendatud link, on ka andmestruktuur, mida saab kasutada elementide kogumi talletamiseks. See koosneb sõlmede jadast ja igal sõlmel on viide järgnevale sõlmele.

Joonisel 1 on kooditükk, mida tavaliselt kasutatakse massiivi väärtuste deklareerimiseks ja määramiseks. Joonis 2 kujutab massiivi väljanägemist mälus.

Eespool olev kood määratleb massiivi, mis mahutab 5 täisarvu ja millele pääseb juurde indeksitega 0 kuni 4. Massiivi üheks oluliseks omaduseks on see, et kogu massiiv eraldatakse ühe mäluplokkina ja iga element saab massiivis oma ruumi. Kui massiiv on määratletud, fikseeritakse selle suurus. Nii et kui te pole kompileerimise ajal massiivi suuruses kindel, peaksite määratlema piisavalt suure massiivi, et see oleks turvalises pooles. Kuid enamasti hakkame tegelikult kasutama vähem elemente, kui oleme eraldanud. Nii kulub tegelikult märkimisväärselt palju mälu. Teisest küljest, kui “piisavalt suur massiiv” pole tegelikult piisavalt suur, siis programm jookseb kokku.

Lingitud loend eraldab mälu oma elementidele eraldi oma mäluplokis ja üldine struktuur saadakse, ühendades need elemendid ahelas linkidena. 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 tähistab ahela järgmist elementi. Lingitud loendi esimene element salvestatakse lingitud loendi pealkirjana.

Joonis 3: Lingitud loendi element

Joonis 4 kujutab lingitud loendit kolme elemendiga. Iga element salvestab oma andmed ja kõik elemendid, välja arvatud viimane, talletab viite järgmisele elemendile. Viimane element hoiab järgmisel väljal nullväärtust. Mis tahes loendi elemendile pääsete juurde, alustades otsast ja järgides järgmist kursorit, kuni vastate nõutavale elemendile.

Ehkki massiivid ja lingitud loendid on sarnased selles mõttes, et neid mõlemaid kasutatakse elementide kogumi talletamiseks, tekivad nendes erinevused, mis tulenevad strateegiast, mida nad kasutavad mälu eraldamiseks selle elementidele. Massiivid eraldavad mälu kõikidele selle elementidele ühe plokkina ja massiivi suurus tuleb käitustähtajana kindlaks määrata. 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 efektiivsem olukordades, kus te ei tea loendi suurust kompileerimise ajal. Deklareerimine ja lingitud loendis olevate elementide juurde pääsemine poleks sirgjooneline võrreldes sellega, kuidas pääsete massiivi elementidele otse juurde oma indekseid kasutades.