Wat is een gekoppelde gegevensstructuur?

Een gekoppelde gegevensstructuur is een verzameling gegevens die zijn gerangschikt in een lijstachtig formaat. Elk stukje datum in de lijst wordt een knooppunt genoemd. Elk knooppunt is verbonden met de volgende op delijst 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 kan groeien of krimpen in de loop vanDe uitvoering van het programma. Het meest voorkomende type gekoppelde gegevensstructuur wordt een gekoppelde lijst genoemd.

Een knooppunt van een gekoppelde gegevensstructuur bevat over het algemeen twee stukken informatie mdash;Een verwijzing naar de werkelijke gegevens die worden opgeslagen en een verwijzing naar het volgende knooppunt op de lijst. Een gekoppelde lijst wordt doorkruist of doorzocht, door elk van de gegevensknooppunten te stappen, beginnend bij de eerste,of het hoofd van de lijst. Er is geen manier om informatie te vinden in een gekoppelde lijst zonder de knooppunten van begin tot eind door de knooppunten te bewegen.

De meeste gekoppelde gegevensstructuren zullen tijdens het programma zo weinig mogelijk geheugen gebruikenuitvoering. Als een gekoppelde lijst wordt gemaakt met slechts één knooppunt en er geen andere knooppunten worden toegevoegd, neemt die lijst het geheugen op dat nodig is voor slechts één knooppunt. Dit is in Starkcontrast met een array -gegevensstructuur waarin de grootte van de gehele array moet worden verklaard en toegewezen aan het begin van het programma en niet kan worden gewijzigd.

Gekoppelde lijsten betalen voor hun efficiënt gebruik van geheugenbronnen door te vereisen.meer rekenkracht. Een specifiek stuk van D vindenATA in een gekoppelde lijst vereist elke keer door de hele lijst door de hele lijst te lopen, dus het kan langzamer zijn om toegang te krijgen tot informatie in het midden van de lijst. Gegevens verwijderen of opnieuw bestellen in een gekoppelde lijst kan ook rekenintensiever zijn dan het beheren van eenarray waarin elementen gemakkelijk kunnen worden verwisseld.

Een gekoppelde gegevensstructuur is niet vereist om slechts één verwijzing naar het volgende knooppunt te hebben;het kan verschillende hebben. Sommige gekoppelde lijsten hebben twee knooppuntreferenties, één naar het volgende knooppunt in de lijst en één naar het vorige knooppunt. Deze staan bekend als dubbel gekoppelde lijsten. Dit kan door een door eenLijst in beide richtingen veel sneller op, hoewel ten koste van het verhoogde 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 vergelijkbaarnaar een boom met hele takken van knooppunten die uit een enkele uiteenlopen. Dit soort gegevensstructuren worden multiply -gekoppelde lijsten genoemd. Multipy gekoppelde lijsten zijn met name nuttig voor complexe sorteeralgoritmen die worden gebruikt om gegevens te structureren.Zoekbomen zijn grotendeels mogelijk vanwege het gebruik van gekoppelde gegevensstructuren om meerdere takken met variabele lengte te maken.