Arrayer lagrar element i sammanhängande minnesplatser, vilket resulterar i lätt beräkningsbara adresser för de lagrade elementen, vilket gör det möjligt att snabbare få tillgång till ett element vid ett visst index. Länkade listor är mindre rigida i sin lagringsstruktur och elementen lagras vanligtvis inte på sammanhängande platser, varför de måste lagras med ytterligare taggar som ger en referens till nästa element. Denna skillnad i datalagringsschema avgör vilken datastruktur som är bäst lämpad för en given situation.

Datalagringsschema för en array

Datalagringsschema för en länkad lista

De viktigaste skillnaderna anges nedan:

• Storlek: Eftersom data endast kan lagras i sammanhängande minnesblock i en array kan dess storlek inte ändras vid körning på grund av risken för överskrivning av andra data. I en länkad lista pekar dock varje nod på nästa så att data kan finnas på spridda (icke sammanhängande) adresser, vilket möjliggör en dynamisk storlek som kan ändras vid körning.
• Minnesallokering: För matriser vid kompileringstid och vid körtid för länkade listor.
• Minneseffektivitet: För samma antal element använder länkade listor mer minne eftersom en referens till nästa nod också lagras tillsammans med data. Flexibiliteten i länkade listor kan dock göra att de totalt sett använder mindre minne; detta är användbart när det råder osäkerhet om storleken eller när det finns stora variationer i dataelementens storlek; minne motsvarande den övre gränsen för storleken måste allokeras (även om inte allt används) vid användning av matriser, medan länkade listor kan öka sina storlekar stegvis proportionellt till datamängden.
• Exekveringstid: Exekveringstid: I en länkad lista måste man dock gå igenom alla tidigare element för att nå ett element. Dessutom kan bättre cachelokalisering i matriser (på grund av sammanhängande minnesallokering) avsevärt förbättra prestandan. Som ett resultat av detta är vissa operationer (t.ex. ändring av ett visst element) snabbare i matriser, medan andra operationer (t.ex. införande/utplåning av ett element i data) är snabbare i länkade listor.

Följande är de punkter som talar för länkade listor.
(1) Arraysens storlek är fast: Vi måste alltså känna till den övre gränsen för antalet element i förväg. Dessutom är det tilldelade minnet i allmänhet lika med den övre gränsen oavsett användning, och vid praktisk användning nås den övre gränsen sällan.

(2) Att infoga ett nytt element i en array av element är dyrt eftersom ett utrymme måste skapas för de nya elementen och för att skapa utrymme måste befintliga element flyttas.

Antag till exempel att vi upprätthåller en sorterad lista med ID-uppgifter i en array id.

id = .

Och om vi vill infoga ett nytt ID 1005 måste vi, för att behålla den sorterade ordningen, flytta alla element efter 1000 (utom 1000).

Släckning är också dyrt med matriser tills om inte några speciella tekniker används. För att till exempel radera 1010 i id måste allt efter 1010 flyttas.

Så länkade listor ger följande två fördelar jämfört med matriser
1) Dynamisk storlek
2) Lätt att infoga/radera

Länkade listor har följande nackdelar:
1) Slumpmässig åtkomst är inte tillåten. Vi måste få tillgång till elementen sekventiellt med början från den första noden. Vi kan alltså inte göra en binär sökning med länkade listor.
2) Extra minnesutrymme för en pekare krävs med varje element i listan.
3) Arrayer har bättre cachelokalitet som kan göra en ganska stor skillnad i prestanda.