Arrays slaan elementen op in aaneengesloten geheugenlocaties, wat resulteert in gemakkelijk berekenbare adressen voor de opgeslagen elementen en dit laat een snellere toegang toe tot een element op een specifieke index. Gekoppelde lijsten zijn minder rigide in hun opslagstructuur en elementen worden gewoonlijk niet op aaneengesloten plaatsen opgeslagen, zodat zij moeten worden opgeslagen met extra tags die een verwijzing naar het volgende element geven. Dit verschil in het schema van gegevensopslag bepaalt welke gegevensstructuur in een gegeven situatie geschikter is.

Gegevensopslagschema van een array

Gegevensopslagschema van een gekoppelde lijst

De belangrijkste verschillen worden hieronder opgesomd:

• Omvang: Aangezien gegevens alleen kunnen worden opgeslagen in aaneengesloten blokken geheugen in een array, kan de grootte ervan niet worden gewijzigd tijdens runtime vanwege het risico van overschrijven over andere gegevens. In een gekoppelde lijst wijst elk knooppunt echter naar het volgende, zodat gegevens op verspreide (niet-aaneengesloten) adressen kunnen bestaan; dit maakt een dynamische grootte mogelijk die tijdens runtime kan veranderen.
• Geheugentoewijzing: Voor arrays bij het compileren en bij runtime voor gelinkte lijsten.
• Geheugenefficiëntie: Voor hetzelfde aantal elementen gebruiken gelinkte lijsten meer geheugen, omdat een verwijzing naar het volgende knooppunt ook samen met de gegevens wordt opgeslagen. De flexibiliteit in de grootte van gelinkte lijsten kan er echter voor zorgen dat zij over het geheel genomen minder geheugen gebruiken; dit is nuttig wanneer er onzekerheid bestaat over de grootte of wanneer er grote variaties zijn in de grootte van de gegevenselementen; bij het gebruik van arrays moet geheugen worden toegewezen dat gelijk is aan de bovengrens van de grootte (zelfs als niet alles wordt gebruikt), terwijl gelinkte lijsten hun grootte stapsgewijs kunnen vergroten naar evenredigheid van de hoeveelheid gegevens.
• Uitvoeringstijd: Elk element in een array kan direct worden benaderd met zijn index; maar in het geval van een gekoppelde lijst moeten alle voorgaande elementen worden doorlopen om elk element te bereiken. Ook kan een betere cache-localiteit in arrays (als gevolg van contigue geheugentoewijzing) de prestaties aanzienlijk verbeteren. Als gevolg hiervan zijn sommige operaties (zoals het wijzigen van een bepaald element) sneller in arrays, terwijl sommige andere (zoals het invoegen/verwijderen van een element in de data) sneller zijn in gelinkte lijsten.

Dit zijn de punten die vóór gekoppelde lijsten pleiten.
(1) De grootte van de arrays ligt vast: we moeten dus van tevoren de bovengrens van het aantal elementen kennen. Bovendien is het toegewezen geheugen in het algemeen gelijk aan de bovengrens, ongeacht het gebruik, en bij praktisch gebruik wordt de bovengrens zelden bereikt.

(2) Het invoegen van een nieuw element in een array van elementen is duur, omdat er ruimte moet worden gemaakt voor de nieuwe elementen en om ruimte te maken moeten bestaande elementen worden verschoven.

Voorbeeld: stel dat we een gesorteerde lijst van ID’s in een array id bijhouden.

id = .

En als we een nieuw ID 1005 willen invoegen, dan moeten we, om de gesorteerde volgorde te handhaven, alle elementen na 1000 (met uitzondering van 1000) verplaatsen.

Wissen is ook duur met arrays, tenzij er speciale technieken worden gebruikt. Bijvoorbeeld, om 1010 in id te verwijderen, moet alles na 1010 worden verplaatst.

Gekoppelde lijsten bieden dus de volgende twee voordelen boven arrays
1) Dynamische grootte
2) Gemak van invoegen/verwijderen

Gekoppelde lijsten hebben de volgende nadelen:
1) Willekeurige toegang is niet toegestaan. We moeten de elementen sequentieel benaderen, te beginnen bij het eerste knooppunt. We kunnen dus geen binaire zoekopdracht uitvoeren met gelinkte lijsten.
2) Bij elk element van de lijst is extra geheugenruimte voor een pointer nodig.
3) Arrays hebben een betere cache-localiteit die een behoorlijk groot verschil in prestaties kan maken.