Arrays vs Linked Lists
Arrays er den mest brukte datastrukturen for å lagre samling av elementer. De fleste programmeringsspråk gir metoder for enkelt å deklarere matriser og få tilgang til elementer i matrisene. Linked list, mer presist enkeltlenket 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 kodestykke som vanligvis brukes til å deklarere og tilordne verdier til en matrise. Figur 2 viser hvordan en matrise vil se ut i minnet.
Over kode definerer en matrise som kan lagre 5 heltall, og de nås ved å bruke indeksene 0 til 4. En viktig egenskap ved 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, er størrelsen fast. Så hvis du ikke er sikker på størrelsen på matrisen på kompileringstidspunktet, må du definere en stor nok matrise til å være på den sikre siden. Men mesteparten av tiden kommer vi faktisk til å bruke mindre antall elementer enn vi har tildelt. Så en betydelig mengde minne er faktisk bortkastet. På den annen side, hvis "stor nok array" faktisk ikke er stor nok, ville programmet krasje.
En koblet liste tildeler minne til elementene separat i sin egen minneblokk, og den overordnede strukturen oppnås ved å koble disse elementene som ledd 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 lagres som hodet på den koblede listen.
| data | neste |
Figur 3: Element av en koblet liste
Figur 4 viser en koblet liste med tre elementer. Hvert element lagrer dataene sine, og alle elementene unntatt det siste lagrer en referanse til det neste elementet. Siste element har en nullverdi i neste felt. Ethvert element i listen kan nås ved å starte på toppen og følge neste peker til du møter det nødvendige elementet.
Selv om arrays 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 å allokere minne til elementene. Matriser allokerer minne til alle elementene som en enkelt blokk, og størrelsen på matrisen må bestemmes under kjøring. Dette vil gjøre arrayene ineffektive i situasjoner der du ikke vet størrelsen på arrayen på kompileringstidspunktet. Siden en koblet liste tildeler minne til elementene separat, ville det være mye effektivt i situasjoner der du ikke vet størrelsen på listen på kompileringstidspunktet. Deklarasjon og tilgang til elementer i en koblet liste vil ikke være rett frem sammenlignet med hvordan du får direkte tilgang til elementer i en matrise ved å bruke indeksene.
