Arrays vs Linked Lists
Arrays er den mest brukte datastrukturen for å lagre innsamling av elementer. De fleste programmeringsspråk gir metoder for å enkelt deklarere matriser og få tilgang til elementer i matriser. Koblet liste, mer presist enkeltkoblet liste, er også en datastruktur som kan brukes til å lagre samling av elementer. Den består av en sekvens av noder, og hver node har en referanse til neste node i sekvensen.
Vist i figur 1, er et stykke kode som vanligvis brukes til å erklære og tildele verdier til en matrise. Figur 2 viser hvordan en matrise vil se ut i minnet.
Ovenfor koden definerer en matrise som kan lagre 5 heltall, og de får tilgang til ved hjelp av indeksene 0 til 4. En viktig egenskap for en matrise er at hele matrisen er allokert som en enkelt minneblokk og hvert element får sin egen plass i matrisen. Når en matrise er definert, blir størrelsen løst. Så hvis du ikke er sikker på størrelsen på matrisen ved kompileringstid, må du definere en stor nok matrise til å være på den sikre siden. Men mesteparten av tiden skal vi faktisk bruke færre antall elementer enn vi har tildelt. Så en betydelig mengde minne er faktisk bortkastet. På den annen side hvis "stort nok array" faktisk ikke er stort nok, vil programmet krasje.
En koblet liste tildeler minne til elementene separat i sin egen hukommelsesblokk, og den generelle strukturen oppnås ved å koble disse elementene som lenker i en kjede. Hvert element i en koblet liste har to felt som vist i figur 3. Datafeltet inneholder de faktiske dataene som er lagret, og det neste feltet inneholder referansen til neste element i kjeden. Det første elementet i den koblede listen er lagret som hodet til den koblede listen.
Figur 3: Element av en koblet liste
Figur 4 viser en koblet liste med tre elementer. Hvert element lagrer dataene og alle elementene unntatt den siste lagrer en referanse til neste element. Siste element har en nullverdi i sitt neste felt. Du kan få tilgang til ethvert element i listen ved å starte på hodet og følge neste peker til du oppfyller ønsket element.
Selv om matriser og koblede lister er like i den forstand at begge brukes til å lagre samling av elementer, pådrar de seg forskjeller på grunn av strategiene de bruker for å tildele minne til elementene. Arrays tildeler minne til alle elementene som en enkelt blokk, og størrelsen på matrisen må bestemmes ved kjøretid. Dette vil gjøre matriser ineffektive i situasjoner der du ikke vet størrelsen på matrisen på kompileringstidspunktet. Siden en lenket liste tildeler minne til elementene hver for seg, vil det være mye effektivt i situasjoner der du ikke vet størrelsen på listen på kompileringstidspunktet. Erklæring og tilgang til elementer i en koblet liste ville ikke være rett frem i forhold til hvordan du direkte får tilgang til elementer i en matrise ved hjelp av indeksene.
