Hva er en koblet datastruktur?
En koblet datastruktur er en samling av data arrangert i et listelignende format. Hvert stykke av dateringer i listen blir referert til som en node. Hver node er koblet til den neste på listen ved å referere til minneadressen til den påfølgende noden. Koblede datastrukturer brukes i stedet for en matrise når antall noder på en liste er ukjent eller kan vokse eller krympe i løpet av Utførelse av programmet. Den vanligste typen koblede datastrukturer kalles en koblet liste.
En knutepunkt for en koblet datastruktur inneholder vanligvis to informasjonsstykker - en referanse til de faktiske dataene som blir lagret og en referanse til neste node på listen. En lenket liste blir krysset, eller søkt, ved å gå inn gjennom hver av dataknodene, begynnende ved den første, eller lederen av listen. Det er ingen måte å finne informasjon i en koblet liste uten å sekvensielt bevege seg gjennom nodene fra begynnelse til slutt.
De fleste koblede datastrukturer vil bruke så lite minne som mulig under programutførelse. Hvis en koblet liste opprettes med bare en node og ingen andre noder legges til, vil den listen ta opp minne som kreves for bare en node. Dette står i sterk kontrast til en matrisedatasstruktur der størrelsen på hele matrisen må deklareres og tildeles ved starten av programmet og ikke kan endres .
Koblede lister betaler for effektiv bruk av minnressurser ved å kreve mer datakraft. Å finne et bestemt stykke data i en koblet liste krever looping gjennom hele listen hver gang, så det kan være tregere å få tilgang til informasjon i midten av listen. Fjerne eller ombestille data i en lenket liste kan også være mer beregningsintensivt enn å håndtere en matrise der elementer enkelt kan byttes.
En koblet datastruktur er ikke påkrevd å bare ha en referanse til neste node; Den kan ha flere. Noen koblede lister har to nodehenvisninger, en til neste node i listen og en til forrige node. Disse er kjent som dobbeltkoblede lister. Dette kan gjøre det mulig å bevege seg gjennom en liste i begge retninger mye raskere, men på bekostning av økt minnebruk for datastrukturen.
Det er mulig for koblede lister å ha tre eller flere referanser til andre noder i listen. Dette skaper en struktur som ligner et tre med hele grener av noder som gytes fra en enkelt. Disse typer data strukturer kalles multipliserte lister. Multiplinerte lister er spesielt nyttige for komplekse sorteringsalgoritmer som brukes til å strukturere data. Søketrær er muligens i stor grad på grunn av bruken av koblede datastrukturer å lage flere grener med variabel lengde.