Arrays vs Sammenkædede lister
Arrays er den mest anvendte datastruktur til at gemme samling af elementer. De fleste programmeringssprog giver metoder til let at erklære arrays og få adgang til elementer i arrays. Sammenkædet liste, mere præcist enkeltkædet liste, er også en datastruktur, der kan bruges til at gemme samling af elementer. Den består af en sekvens af noder, og hver node har en henvisning til den næste node i sekvensen.
Vist i figur 1 er et stykke kode, der typisk bruges til at deklarere og tildele værdier til en matrix. Figur 2 viser, hvordan en matrix vil se ud i hukommelsen.
Ovenstående kode definerer en matrix, der kan lagre 5 heltal, og de fås adgang til ved hjælp af indeks 0 til 4. En vigtig egenskab ved en matrix er, at hele arrayet er allokeret som en enkelt hukommelsesblok, og hvert element får sit eget rum i arrayet. Når en matrix er defineret, er dens størrelse rettet. Så hvis du ikke er sikker på størrelsen af arrayet på kompileringstidspunktet, bliver du nødt til at definere en stor nok array til at være i den sikre side. Men det meste af tiden vil vi faktisk bruge færre antal elementer, end vi har tildelt. Så en betydelig mængde hukommelse spildes faktisk. På den anden side, hvis "stort nok array" faktisk ikke er stort nok, ville programmet gå ned.
En sammenkædet liste tildeler hukommelse til sine elementer separat i sin egen hukommelsesblok, og den samlede struktur opnås ved at forbinde disse elementer som led i en kæde. Hvert element i en sammenkædet liste har to felter som vist i figur 3. Datafeltet indeholder de faktisk lagrede data, og det næste felt indeholder henvisningen til det næste element i kæden. Det første element på den sammenkædede liste er gemt som hovedet på den sammenkædede liste.
Figur 3: Element af en sammenkædet liste
Figur 4 viser en sammenkædet liste med tre elementer. Hvert element gemmer sine data og alle elementer undtagen det sidste gemmer en henvisning til det næste element. Sidste element har en nulværdi i det næste felt. Du kan få adgang til ethvert element på listen ved at starte ved hovedet og følge den næste markør, indtil du møder det krævede element.
Selvom arrays og sammenkædede lister er ens i den forstand, at de begge bruges til at gemme samling af elementer, medfører de forskelle på grund af de strategier, de bruger til at allokere hukommelse til dets elementer. Arrays tildeler hukommelse til alle dens elementer som en enkelt blok, og arrayets størrelse skal bestemmes ved kørselstid. Dette ville gøre arrays ineffektive i situationer, hvor du ikke kender arrayets størrelse på kompileringstidspunktet. Da en sammenkædet liste tildeler hukommelse til sine elementer separat, ville det være meget effektivt i situationer, hvor du ikke kender størrelsen på listen på kompileringstidspunktet. Erklæring og adgang til elementer i en sammenkædet liste ville ikke være ligetil sammenlignet med hvordan du direkte får adgang til elementer i et array ved hjælp af dets indekser.
