Arrays vs Linked Lists
Arrays er den mest almindeligt anvendte datastruktur til at gemme samling af elementer. De fleste programmeringssprog giver metoder til nemt at erklære arrays og få adgang til elementer i arrays. Sammenkædet liste, mere præcist enkelt-linket 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 reference til den næste node i sekvensen.
vist i figur 1, er et stykke kode, der typisk bruges til at erklære og tildele værdier til en matrix. Figur 2 viser, hvordan et array ville se ud i hukommelsen.
Ovenstående kode definerer et array, der kan lagre 5 heltal, og de tilgås ved hjælp af indeks 0 til 4. En vigtig egenskab ved et array er, at hele array 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 fast. Så hvis du ikke er sikker på størrelsen af arrayet på kompileringstidspunktet, skal du definere et stort nok array til at være på den sikre side. Men det meste af tiden kommer vi faktisk til at bruge mindre antal elementer, end vi har tildelt. Så en betydelig mængde hukommelse er faktisk spildt. På den anden side, hvis det "store nok array" faktisk ikke er stort nok, ville programmet gå ned.
En sammenkædet liste allokerer hukommelse til sine elementer separat i sin egen hukommelsesblok, og den overordnede 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 faktiske data, der er gemt, og det næste felt indeholder referencen til det næste element i kæden. Det første element i den linkede liste gemmes som hovedet på den linkede liste.
| data | next |
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 reference til det næste element. Sidste element har en nulværdi i dets næste felt. Ethvert element på listen kan tilgås ved at starte ved hovedet og følge den næste markør, indtil du opfylder det nødvendige element.
Selv om arrays og linkede 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 allokerer hukommelse til alle dens elementer som en enkelt blok, og størrelsen af arrayet skal bestemmes ved kørsel. Dette ville gøre arrays ineffektive i situationer, hvor du ikke kender størrelsen af arrayet på kompileringstidspunktet. Da en sammenkædet liste allokerer hukommelse til dens elementer separat, ville det være meget effektivt i situationer, hvor du ikke kender størrelsen af listen på kompileringstidspunktet. Deklaration 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.
