Arrays versus gekoppelde lijsten
Arrays zijn de meest gebruikte gegevensstructuur om verzameling elementen op te slaan. De meeste programmeertalen bieden methoden om arrays eenvoudig te declareren en toegang te krijgen tot elementen in de arrays. Gekoppelde 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 aan een array te declareren en toe te wijzen. Figuur 2 laat zien hoe een array eruit zou zien in het geheugen.
Bovenstaande code definieert een array die 5 gehele getallen kan opslaan en deze worden benaderd met behulp van indices 0 tot 4. Een belangrijke eigenschap van een array is dat de hele array wordt toegewezen als een enkel geheugenblok en dat elk element zijn eigen ruimte in de array krijgt. Zodra een array is gedefinieerd, staat de grootte ervan vast. Dus als je niet zeker bent van de grootte van de array tijdens het compileren, dan zou je een array moeten definiëren die groot genoeg is om aan de veilige kant te blijven. Maar meestal gaan we eigenlijk minder elementen gebruiken dan we hebben toegewezen. Er wordt dus een aanzienlijke hoeveelheid geheugen verspild. Aan de andere kant, als de "groot genoeg array" niet echt groot genoeg is, crasht het programma.
Een gekoppelde lijst wijst geheugen toe aan zijn elementen afzonderlijk in zijn eigen geheugenblok en de algehele structuur wordt verkregen door deze elementen als schakels in een ketting te verbinden. Elk element in een gekoppelde lijst heeft twee velden, zoals weergegeven in Figuur 3. Het dataveld bevat de feitelijke gegevens die zijn opgeslagen 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.
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 het 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 kan worden geopend door bij het hoofd te beginnen en de volgende aanwijzer te volgen totdat u het vereiste element ontmoet.
Hoewel de arrays en gekoppelde lijsten vergelijkbaar zijn in de zin dat ze allebei 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 tijdens het compileren niet weet. 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 tijdens het compileren niet weet. 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 ervan.
