Forskel mellem matriser og tilknyttede lister

Arrays vs linkede lister

Arrays er den mest almindeligt anvendte datastruktur til lagring af samling af elementer. De fleste programmeringssprog indeholder metoder til let at deklarere arrays og adgangselementer i arrays. Kæ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 knudepunkter, og hver knude har en henvisning til den næste knude i sekvensen.

I figur 1 vises et stykke kode, der typisk bruges til at erklære og tildele værdier til en matrix. Figur 2 viser, hvordan en matrix ville se ud i hukommelsen.

Ovenfor kode definerer en matrix, der kan gemme 5 heltal, og der fås adgang til dem ved hjælp af indekser 0 til 4. En vigtig egenskab ved en matrix er, at hele matrix er tildelt som en enkelt hukommelsesblok, og hvert element får sin egen plads i matrixen. Når en matrix er defineret, er dens størrelse fast. Så hvis du ikke er sikker på størrelsen på matrixen på kompileringstidspunktet, bliver du nødt til at definere en stor nok matrix til at være i den sikre side. Men for det meste bruger vi faktisk mindre antal elementer, end vi har tildelt. Så en betydelig mængde hukommelse spildes faktisk. På den anden side, hvis det "store nok array" faktisk ikke er stort nok, ville programmet gå ned.

En tilknyttet liste tildeler hukommelse til dens elementer separat i sin egen hukommelsesblok, og den samlede struktur opnås ved at linke disse elementer som links i en kæde. Hvert element i en sammenkoblet liste har to felter som vist i figur 3. Datafeltet indeholder de faktiske data, der er gemt, og det næste felt indeholder henvisningen til det næste element i kæden. Det første element i den tilknyttede liste gemmes som hovedet på den tilknyttede liste.

Figur 3: Element i en knyttet liste

Figur 4 viser en sammenkoblet 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 nullværdi i det næste felt. Ethvert element på listen kan fås ved at starte ved hovedet og følge den næste markør, indtil du opfylder det krævede element.

Selvom matriserne og sammenkoblede lister er ens i den forstand, at begge af dem bruges til at gemme samling af elementer, har de forskelle på grund af de strategier, de bruger til at allokere hukommelse til dens elementer. Arrays tildeler hukommelse til alle dens elementer som en enkelt blok, og størrelsen på arrayet skal bestemmes ved kørsel. Dette ville gøre matriserne ineffektive i situationer, hvor du ikke kender størrelsen på matrixen på kompileringstidspunktet. Da en tilknyttet liste tildeler hukommelse til dens elementer separat, ville den være meget effektiv i situationer, hvor du ikke ved størrelsen på listen på kompileringstidspunktet. Erklæring og adgang til elementer i en linket liste ville ikke være ligetil sammenlignet med hvordan du direkte får adgang til elementer i en matrix ved hjælp af dens indekser.