Verschil tussen arrays en gekoppelde lijsten

Arrays versus gekoppelde lijsten

Arrays zijn de meest gebruikte gegevensstructuur voor het opslaan van elementen. De meeste programmeertalen bieden methoden voor het eenvoudig declareren van arrays en toegangselementen in de arrays. Gekoppelde lijst, meer specifiek enkelvoudig gekoppelde lijst, is ook een gegevensstructuur die kan worden gebruikt om 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 typisch wordt gebruikt om waarden aan een array te declareren en toe te wijzen. Figuur 2 geeft weer hoe een array eruit zou zien in het geheugen.

Bovenstaande code definieert een array die 5 gehele getallen kan opslaan en deze wordt benaderd met behulp van indices 0 tot 4. Een belangrijke eigenschap van een array is dat de gehele array wordt toegewezen als een enkel geheugenblok en elk element zijn eigen ruimte in de array krijgt. Zodra een array is gedefinieerd, is de grootte ervan vastgesteld. Dus als je niet zeker bent over de grootte van de array tijdens het compileren, zou je een array moeten definiëren die groot genoeg is om veilig te zijn. Maar meestal gaan we minder elementen gebruiken dan we hebben toegewezen. Dus een aanzienlijke hoeveelheid geheugen is eigenlijk verspild. Aan de andere kant crasht het programma als de "groot genoeg array" niet groot genoeg is.

Een gelinkte lijst wijst geheugen aan zijn elementen afzonderlijk toe in zijn eigen geheugenblok en de algehele structuur wordt verkregen door deze elementen als schakels in een keten te verbinden. Elk element in een gekoppelde lijst heeft twee velden zoals weergegeven in figuur 3. Het gegevensveld 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 gelinkte lijst

Figuur 4 toont een gekoppelde lijst met drie elementen. Elk element slaat zijn gegevens op en alle elementen, behalve het laatste, hebben een verwijzing naar het volgende element. Laatste element bevat een nulwaarde in zijn volgende veld. Elk element in de lijst is toegankelijk door te beginnen bij de kop en de volgende aanwijzer te volgen totdat u aan het vereiste element voldoet.

Hoewel de arrays en gekoppelde lijsten vergelijkbaar zijn in de zin dat ze allebei worden gebruikt om een ​​verzameling elementen op te slaan, maken ze verschillen vanwege de strategieën die ze gebruiken om geheugen aan de elementen toe te wijzen. Arrays wijzen geheugen toe aan alle 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 gelinkte lijst geheugen aan zijn elementen afzonderlijk 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 gelinkte lijst zou niet eenvoudig zijn in vergelijking met hoe u rechtstreeks toegang hebt tot elementen in een array met behulp van zijn indexen.