Skillnad mellan Arrays och Linked Lists

Arrays vs Linked Lists

Arrays är den vanligaste datastrukturen för att lagra samling av element. De flesta programmeringsspråk ger metoder för att enkelt deklarera arrayer och åtkomstelement i arraysna. Länkade lista, mer exakt ensam lä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.

Visad i figur 1 är ett kodstycke 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.

Ovanstående kod definierar en array som kan lagra 5 heltal och de nås med indexerna 0 till 4. En viktig egenskap hos en array är att hela arrayen allokeras som ett enda block av minne och varje element får sitt eget utrymme i arrayen. När en array är definierad, är dess storlek fixerad. Så om du inte är säker på storleken på matrisen vid sammanställningstiden måste du definiera en tillräckligt stor matris för att vara i den säkra sidan. Men mestadels kommer vi faktiskt att använda mindre antal element än vad vi har tilldelat. Så en stor mängd minne är faktiskt bortkastat. Å andra sidan om "tillräckligt stor matris" inte är tillräckligt stor nog skulle programmet krascha.

En länkad lista allokerar minne till dess 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 de faktiska data som lagras och nästa fält innehåller referensen till nästa element i kedjan. Det första elementet i den länkade listan sparas som huvudet på den länkade listan.

Figur 3: Element av en länkad lista

Figur 4 visar en länkad lista med tre element. Varje element lagrar sin 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 i huvudet och följa nästa pekare tills du uppfyller det önskade elementet.

Även om arrays och länkade listor är lika i den meningen att 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 allokera minne till dess element. Arrays 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 sammanställningstiden. Eftersom en länkad lista allokerar minne till dess element separat, skulle det vara mycket effektivt i situationer där du inte känner till storleken på listan vid sammanställningstiden. Deklaration och tillgång till element i en länkad lista skulle inte vara rakt framåt jämfört med hur du direkt åtkomst till element i en array med dess index.