Arrays versus gekoppelde lijsten
Arrays zijn de meest gebruikte gegevensstructuur om een verzameling elementen op te slaan. De meeste programmeertalen bieden methoden om eenvoudig arrays te declareren en toegang te krijgen tot elementen in de arrays. Gelinkte lijst, meer bepaald enkelvoudig gekoppelde lijst, is ook een gegevensstructuur die kan worden gebruikt om een verzameling elementen op te slaan. Het bestaat uit een reeks knooppunten en elk knooppunt heeft een verwijzing naar het volgende knooppunt in de reeks.
Getoond in figuur 1 is een stukje code dat doorgaans wordt gebruikt om waarden te declareren en toe te wijzen aan een array. Afbeelding 2 laat zien hoe een array eruit zou zien in het geheugen.
Bovenstaande code definieert een array die 5 gehele getallen kan opslaan en ze zijn toegankelijk met indices 0 tot 4. Een belangrijke eigenschap van een array is dat de hele array wordt toegewezen als een enkel geheugenblok en elk element zijn eigen ruimte krijgt in de reeks. Zodra een array is gedefinieerd, ligt de grootte vast. Dus als u niet zeker bent over de grootte van de array tijdens het compileren, moet u een array definiëren die groot genoeg is om aan de veilige kant te blijven. Maar meestal gaan we minder elementen gebruiken dan we hebben toegewezen. Er wordt dus een aanzienlijke hoeveelheid geheugen verspild. Aan de andere kant, als de "matrix groot genoeg" niet echt groot genoeg is, zou het programma crashen.
Een gekoppelde lijst wijst geheugen toe aan zijn elementen afzonderlijk in zijn eigen geheugenblok en de algemene structuur wordt verkregen door deze elementen als schakels in een ketting te koppelen. Elk element in een gekoppelde lijst heeft twee velden, zoals weergegeven in figuur 3. Het gegevensveld bevat de daadwerkelijke opgeslagen gegevens en het volgende veld bevat de verwijzing naar het volgende element in de keten. Het eerste element van de gekoppelde lijst wordt opgeslagen als de kop van de gekoppelde lijst.
| gegevens | volgende |
Figuur 3: Element van een gekoppelde lijst
Figuur 4 toont een gekoppelde lijst met drie elementen. Elk element slaat zijn gegevens op en alle elementen behalve de laatste slaan een verwijzing op naar het volgende element. Het laatste element bevat een null-waarde in het volgende veld. Elk element in de lijst is toegankelijk door bij de kop te beginnen en de volgende aanwijzer te volgen totdat u aan het vereiste element voldoet.
Hoewel de arrays en gelinkte lijsten vergelijkbaar zijn in die zin dat ze beide worden gebruikt om een verzameling elementen op te slaan, lopen ze verschillen op vanwege de strategieën die ze gebruiken om geheugen aan de elementen toe te wijzen. Arrays wijzen geheugen toe aan al zijn elementen als een enkel blok en de grootte van de array moet tijdens runtime worden bepaald. Dit zou de arrays inefficiënt maken in situaties waarin u de grootte van de array niet weet tijdens het compileren. Aangezien een gekoppelde lijst geheugen afzonderlijk aan zijn elementen toewijst, zou het veel efficiënt zijn in situaties waarin u de grootte van de lijst niet weet tijdens het compileren. Declaratie en toegang tot elementen in een gekoppelde lijst zou niet eenvoudig zijn in vergelijking met hoe u rechtstreeks toegang krijgt tot elementen in een array met behulp van de indices.
