Hva er en koblet datastruktur?
En koblet datastruktur er en samling av data arrangert i et liste-lignende format. Hvert stykke punkt på listen blir referert til som en node. Hver node er koblet til den neste påListe ved en henvisning til minneadressen til den påfølgende noden. Koblede datastrukturer brukes i stedet for en matrise når antallet noder på en liste er ukjent eller kan vokse eller krympe i løpet av løpet avUtførelsen av programmet. Den vanligste typen koblet datastruktur kalles en koblet liste.
En node av en koblet datastruktur inneholder vanligvis to informasjonsdeler og mdash;En henvisning til de faktiske dataene som lagres og en referanse til neste node på listen. En koblet liste blir krysset, eller søkt, ved å gå gjennom hver av dataknuter, som begynner på den første,,eller sjefen for listen. Det er ingen måte å finne informasjon i en koblet liste uten å bevege seg i rekkefølge gjennom nodene fra begynnelse til slutt.
De fleste koblede datastrukturer vil bruke så lite minne som mulig under programmetUtførelse. Hvis en koblet liste opprettes med bare en node og ingen andre noder er lagt til, vil listen ta opp minnet som kreves for bare en node. Dette er i StarkKontrast til en array -datastruktur der størrelsen på hele arraymer datakraft. Finne et bestemt stykke DATA i en koblet liste krever looping gjennom hele listen hver gang, slik at det kan være tregere å få tilgang til informasjon midt på listen. Fjerning eller ombestilling av data i en koblet liste kan også være mer beregningsintensiv enn å administrere enArray hvor elementer kan byttes enkelt.
En koblet datastruktur er ikke nødvendig for å ha bare en referanse til neste node;den kan ha flere. Noen koblede lister har to node -referanser, en til neste node i listen og en til forrige node. Disse er kjent som dobbelt koblede lister. Dette kan gjøre å bevege seg gjennom enliste 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 lignende strukturtil et tre med hele grener av noder som gyter fra en enkelt. Disse typer datastrukturer kalles multipliser lenker.Søketrær er i stor grad mulig på grunn av bruk av koblede datastrukturer for å lage flere grener med variabel lengde.