Wat is een gekoppelde gegevensstructuur?
Een gekoppelde gegevensstructuur is een verzameling gegevens die in een lijstachtige indeling zijn gerangschikt. Elk stuk gegevens in de lijst wordt een knooppunt genoemd. Elk knooppunt is verbonden met het volgende op de lijst door een verwijzing naar het geheugenadres van dat volgende knooppunt. Gekoppelde gegevensstructuren worden gebruikt in plaats van een array wanneer het aantal knooppunten op een lijst onbekend is of in de loop van de uitvoering van het programma Het meest voorkomende type gekoppelde gegevensstructuur wordt een gekoppelde lijst genoemd.
Een knooppunt van een gekoppelde datastructuur bevat doorgaans twee stukjes informatie - een verwijzing naar de feitelijke gegevens die worden opgeslagen en een verwijzing naar het volgende knooppunt in de lijst. Een gekoppelde lijst wordt doorlopen of doorzocht door te stappen via elk van de gegevensknooppunten, beginnend bij de eerste, of het hoofd van de lijst. Er is geen manier om informatie in een gekoppelde lijst te vinden zonder achtereenvolgens door de knooppunten van begin tot eind te gaan.
De meeste gekoppelde datastructuren zullen zo weinig mogelijk geheugen gebruiken tijdens de uitvoering van het programma. Als een gekoppelde lijst wordt gemaakt met slechts één knooppunt en er geen andere knooppunten worden toegevoegd, neemt die lijst de geheugen vereist voor slechts één knooppunt. Dit staat in schril contrast met een array-datastructuur waarin de grootte van de hele array moet worden gedeclareerd en toegewezen aan het begin van het programma en niet kan worden gewijzigd. .
Gekoppelde lijsten betalen voor hun efficiënte gebruik van geheugenbronnen door meer rekenkracht te vereisen. Het vinden van een specifiek stuk gegevens in een gekoppelde lijst vereist dat de hele lijst telkens wordt doorlopen, dus het kan langzamer zijn om toegang te krijgen tot informatie in Het verwijderen of herschikken van gegevens in een gekoppelde lijst kan ook computerintensiever zijn dan het beheren van een array waarin elementen eenvoudig kunnen worden verwisseld.
Een gekoppelde gegevensstructuur hoeft niet slechts één verwijzing naar het volgende knooppunt te hebben; het kan er meerdere zijn. Sommige gekoppelde lijsten hebben twee knooppuntverwijzingen, een naar het volgende knooppunt in de lijst en een naar het vorige knooppunt. Dit worden dubbel gekoppelde lijsten genoemd. lijst in beide richtingen veel sneller, hoewel dit ten koste gaat van meer geheugengebruik voor de gegevensstructuur.
Het is mogelijk dat gekoppelde lijsten drie of meer verwijzingen naar andere knooppunten in de lijst hebben.Dit creëert een structuur vergelijkbaar met een boom met hele takken knooppunten die uit één enkele worden voortgebracht. structuren worden multiply linked-lijsten genoemd. Multiply-linked lijsten zijn met name handig voor complexe sorteeralgoritmen die worden gebruikt om gegevens te structureren. Zoekbomen zijn grotendeels mogelijk door het gebruik van gekoppelde datastructuren om meerdere takken met variabele lengte te maken.