Hvad er en knyttet datastruktur?

En sammenkoblet datastruktur er en samling af data arrangeret i et listelignende format. Hvert stykke af punktum på listen kaldes en knude. Hver knude er forbundet til det næste på listen ved hjælp af en henvisning til hukommelsesadressen til den efterfølgende knude. Koblede datastrukturer bruges i stedet for en matrix, når antallet af noder på en liste er ukendt eller muligvis vokser eller krymper i løbet af udførelse af programmet.Den mest almindelige type linket datastruktur kaldes en linket liste.

En knude til en sammenkoblet datastruktur indeholder generelt to oplysninger - en henvisning til de faktiske data, der gemmes, og en henvisning til den næste node på listen. En sammenkædet liste gennemgås eller søges ved at træde gennem hver af dataknudepunkterne, der begynder ved den første, eller lederen af ​​listen. Der er ingen måde at finde information på en sammenkoblet liste uden sekventielt at bevæge sig gennem noderne fra begyndelse til slutning.

De fleste sammenkoblede datastrukturer bruger så lidt hukommelse som muligt under programudførelse. Hvis der oprettes en linket liste med kun en node og ingen andre noder tilføjes, optager denne liste hukommelse, der kræves til kun en knude. Dette er i skarp kontrast til en array-datastruktur, hvor størrelsen på hele arrayen skal deklareres og tildeles ved starten af ​​programmet og ikke kan ændres .

Tilknyttede lister betaler for deres effektive brug af hukommelsesressourcer ved at kræve mere computerkraft. At finde et specifikt stykke data på en linket liste kræver looping gennem hele listen hver gang, så det kan være langsommere at få adgang til oplysninger i midten af ​​listen. Fjernelse eller ombestilling af data i en linket liste kan også være mere beregningsintensivt end at styre en matrix, hvor elementer let kan udskiftes.

En sammenkoblet datastruktur er ikke påkrævet kun at have en henvisning til den næste node; Det kan have flere. Nogle tilknyttede lister har to nodehenvisninger, en til den næste knude på listen og en til den forrige knude. Disse er kendt som dobbeltkædede lister. Dette kan gøre det muligt at bevæge sig gennem en liste i begge retninger meget hurtigere, men på bekostning af øget hukommelsesforbrug til datastrukturen.

Det er muligt for tilknyttede lister at have tre eller flere henvisninger til andre noder på listen.Dette skaber en struktur, der ligner et træ med hele grene af noder, der gyder fra en enkelt. Disse typer data strukturer kaldes multipliserede lister Multipliserede lister er især nyttige til komplekse sorteringsalgoritmer, der bruges til at strukturere data. Søgetræer er stort set mulige på grund af brugen af ​​linkede datastrukturer at oprette flere grene med variabel længde.