Massiivid vs lingitud loendid
Massiivid on kõige sagedamini kasutatav andmestruktuur elementide kogumite salvestamiseks. Enamik programmeerimiskeeli pakuvad meetodeid massiivide hõlpsaks deklareerimiseks ja massiivi elementidele juurdepääsuks. Lingitud loend, täpsem alt üksikult lingitud loend, on ka andmestruktuur, mida saab kasutada elementide kogumi salvestamiseks. See koosneb sõlmede jadast ja igal sõlmel on viide jada järgmisele sõlmele.
Joonisel 1 kujutatud kooditükk, mida tavaliselt kasutatakse massiivi väärtuste deklareerimiseks ja määramiseks. Joonisel 2 on kujutatud, kuidas massiiv mälus välja näeks.
Ül altoodud kood määratleb massiivi, mis suudab salvestada 5 täisarvu ja millele 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 oma ruumi massiivi. Kui massiiv on määratletud, on selle suurus fikseeritud. Seega, kui te pole kompileerimise ajal massiivi suuruses kindel, peaksite defineerima piisav alt suure massiivi, et olla turvalises pooles. Kuid enamasti kasutame me tegelikult vähem elemente, kui oleme eraldanud. Seega kulub märkimisväärne hulk mälu tegelikult raisku. Teisest küljest, kui "piisav alt suur massiiv" pole tegelikult piisav alt suur, jookseb programm kokku.
Lingitud loend eraldab mälu oma elementidele eraldi oma mäluplokis ja üldine struktuur saadakse nende elementide linkimisel ahela 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 sisaldab viidet ahela järgmisele elemendile. Lingitud loendi esimene element salvestatakse lingitud loendi peana.
| andmed | järgmine |
Joonis 3: Lingitud loendi element
Joonis 4 kujutab kolmest elemendist koosnevat lingitud loendit. Iga element salvestab oma andmed ja kõik elemendid peale viimase salvestavad viite järgmisele elemendile. Viimasel elemendil on järgmisel väljal nullväärtus. Loendi igale elemendile pääseb juurde, alustades päisest ja järgides järgmist kursorit, kuni leiate nõutava elemendi.
Kuigi massiivid ja lingitud loendid on sarnased selles mõttes, et neid mõlemaid kasutatakse elementide kogumi salvestamiseks, on neil erinevusi strateegiate tõttu, mida nad oma elementidele mälu eraldamiseks kasutavad. Massiivid eraldavad mälu kõikidele oma elementidele ühe plokina ja massiivi suurus tuleb määrata käitusajal. See muudaks massiivid ebatõhusaks olukordades, kus te ei tea massiivi suurust kompileerimise ajal. Kuna lingitud loend eraldab oma elementidele eraldi mälu, oleks see palju tõhus olukordades, kus te ei tea loendi suurust kompileerimise ajal. Lingitud loendis olevate elementide deklareerimine ja juurdepääs ei oleks lihtne võrreldes sellega, kuidas saate massiivi elementidele selle indekseid kasutades otse juurde pääseda.
