Arrays vs Linked Lists
Arrayer är den mest använda datastrukturen för att lagra samling av element. De flesta programmeringsspråk tillhandahåller metoder för att enkelt deklarera arrayer och komma åt element i arrayerna. Länkad lista, närmare bestämt enkellänkad lista, är också en datastruktur som kan användas för att lagra samling av element. Den består av en sekvens av noder och varje nod har en referens till nästa nod i sekvensen.
Visas i figur 1, är en kodbit som vanligtvis används för att deklarera och tilldela värden till en array. Figur 2 visar hur en array skulle se ut i minnet.
Koden ovan 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 array väl har definierats är dess storlek fast. Så om du inte är säker på storleken på arrayen vid kompilering, måste du definiera en tillräckligt stor array 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 ansenlig mängd minne går faktiskt till spillo. Å andra sidan, om "tillräckligt stor array" faktiskt inte är tillräckligt stor, skulle programmet krascha.
En länkad lista allokerar minne till sina element separat i sitt eget minnesblock och den övergripande 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 data som är lagrad 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 huvudet på den länkade listan.
| data | next |
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 det 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 det obligatoriska elementet.
Även om arrayerna och de länkade listorna är lika i den meningen att de båda används för att lagra samling av element, uppstår skillnader på grund av de strategier de använder för att allokera minne till dess element. Arrayer allokerar minne till alla dess element som ett enda block och storleken på arrayen måste bestämmas vid körning. Detta skulle göra arrayerna ineffektiva i situationer där du inte vet storleken på arrayen vid kompileringstillfället. Eftersom en länkad lista allokerar minne till dess element separat, skulle det vara mycket effektivt i situationer där du inte vet storleken på listan vid kompileringstillfället. Deklaration och åtkomst till element i en länkad lista skulle inte vara enkelt jämfört med hur du direkt kommer åt element i en array med hjälp av dess index.
