Arrays vs länkade listor
Arrayer är den mest använda datastrukturen för att lagra insamling av element. De flesta programmeringsspråk tillhandahåller metoder för att enkelt deklarera matriser och komma åt element i matriserna. Länkad lista, närmare bestämt enskild länkad lista, är också en datastruktur som kan användas för att lagra insamling av element. Den består av en sekvens av noder och varje nod har en referens till nästa nod i sekvensen.
Visad i figur 1 är en kod som vanligtvis används för att deklarera och tilldela värden till en matris. Figur 2 visar hur en matris skulle se ut i minnet.
Ovanstående kod definierar en array som kan lagra 5 heltal och de nås med hjälp av index 0 till 4. En viktig egenskap hos en array är att hela arrayen allokeras som ett enda minnesblock och varje element får sitt eget utrymme i arrayen. När en matris har definierats är dess storlek fixad. Så om du inte är säker på storleken på matrisen vid sammanställningstid, måste du definiera en tillräckligt stor matris för att vara på den säkra sidan. Men för det mesta kommer vi faktiskt att använda mindre antal element än vi har tilldelat. Så en stor mängd minne slösas faktiskt bort. Å andra sidan om "tillräckligt stor matris" inte är tillräckligt stor skulle programmet krascha.
En länkad lista tilldelar minne till sina element separat i sitt eget minnesblock och den totala strukturen erhålls genom att länka dessa element som länkar i en kedja. Varje element i en länkad lista har två fält som visas i figur 3. Datafältet innehåller den faktiska lagrade informationen och nästa fält innehåller referensen till nästa element i kedjan. Det första elementet i den länkade listan lagras som huvud för den länkade listan.
Figur 3: Element i en länkad lista
Figur 4 visar en länkad lista med tre element. Varje element lagrar sina data och alla element utom den sista lagrar en referens till nästa element. Det sista elementet har ett nollvärde i nästa fält. Alla element i listan kan nås genom att börja vid huvudet och följa nästa pekare tills du uppfyller önskat element.
Även om matriserna och länkade listor är lika i den meningen att de båda används för att lagra samling av element, uppstår de skillnader på grund av de strategier de använder för att fördela minne till dess element. Arrays fördelar minne till alla dess element som ett enda block och storleken på arrayen måste bestämmas vid körning. Detta skulle göra matriserna ineffektiva i situationer där du inte känner till storleken på matrisen vid sammanställningstid. Eftersom en länkad lista tilldelar minne till sina element separat, skulle det vara mycket effektivt i situationer där du inte känner till listans storlek vid sammanställning. Deklaration och åtkomst till element i en länkad lista skulle inte vara rakt framåt jämfört med hur du direkt får åtkomst till element i en matris med hjälp av dess index.
