Vad är en länkad datastruktur?

En länkad datastruktur är en samling av data arrangerade i ett listliknande format. Varje nollpunkt i listan kallas en nod. Varje nod är ansluten till nästa på listan genom en hänvisning till minnesadressen för den efterföljande noden. Länkade datastrukturer används i stället för en matris när antalet noder på en lista är okänt eller kan växa eller krympa under loppet av körning av programmet Den vanligaste typen av länkad datastruktur kallas en länkad lista.

En nod i en länkad datastruktur innehåller vanligtvis två informationsdelar - en referens till den faktiska datan som lagras och en referens till nästa nod på listan. En länkad lista går igenom eller sökas genom att kliva genom var och en av datanoderna, som börjar vid den första eller listans huvud. Det finns inget sätt att hitta information i en länkad lista utan att sekventiellt flytta igenom noderna från början till slut.

De flesta länkade datastrukturer använder så lite minne som möjligt under körning av programmet. Om en länkad lista skapas med bara en nod och inga andra noder läggs till kommer den listan att ta upp minne som krävs för endast en nod. Detta står i skarp kontrast till en matrisdatastruktur där storleken på hela matrisen måste deklareras och tilldelas i början av programmet och inte kan ändras .

Länkade listor betalar för deras effektiva användning av minnesresurser genom att kräva mer datorkraft. Att hitta en specifik datainformation i en länkad lista kräver loopning genom hela listan varje gång, så det kan vara långsammare att få tillgång till information i i mitten av listan. Ta bort eller ordna om data i en länkad lista kan också vara mer beräkningsintensiva än att hantera en matris där element enkelt kan bytas.

En länkad datastruktur krävs inte att endast ha en referens till nästa nod; Det kan ha flera. Vissa länkade listor har två nodreferenser, en till nästa nod i listan och en till föregående nod. Dessa är kända som dubbellänkade listor. Detta kan göra att man flyttar igenom en lista i endera riktningen mycket snabbare, men på bekostnad av ökad minnesanvändning för datastrukturen.

Det är möjligt för länkade listor att ha tre eller flera referenser till andra noder i listan. Detta skapar en struktur som liknar ett träd med hela grenar av noder som gyter från en enda. Dessa typer av data strukturer kallas multiplicerade listor. Multiplicerade lister är särskilt användbara för komplexa sorteringsalgoritmer som används för att strukturera data. Sökträd är till stor del möjliga på grund av användningen av länkade datastrukturer för att skapa flera grenar med variabel längd.