Vad är en länkad datastruktur?
En länkad datastruktur är en samling data arrangerade i ett listliknande format. Varje datum i listan kallas en nod. Varje nod är ansluten till nästa påLista med 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änd eller kan växa eller krympa över loppet avexekveringen av programmet. Den vanligaste typen av länkad datastruktur kallas en länkad lista.
En nod av en länkad datastruktur innehåller vanligtvis två informationsdelar och mdash;En hänvisning till de faktiska uppgifterna som lagras och en hänvisning till nästa nod på listan. En länkad lista är korsad eller söks genom att gå igenom var och en av datatoderna, som börjar vid den första,eller chefen för listan. Det finns inget sätt att hitta information i en länkad lista utan att i följd rörelse genom noderna från början till slut.
De flesta länkade datastrukturer kommer att använda så lite minne som möjligt under programmetkörning. Om en länkad lista skapas med endast en nod och inga andra noder läggs till kommer listan att ta upp minnet som krävs för endast en nod. Detta är i Starki kontrast till en matrisdatastruktur där storleken på hela matrisen måste deklareras och tilldelas i början av programmet och kan inte ändras.
Länkade listor betalar för deras effektiva användning av minnesresurser genom att krävamer datorkraft. Hitta en specifik del av DATA i en länkad lista kräver slingor genom hela listan varje gång, så det kan vara långsammare att komma åt information mitt i listan. Att ta bort eller ombeställa data i en länkad lista kan också vara mer beräkningsintensivt än att hantera enArray där element kan bytas enkelt.
En länkad datastruktur krävs inte att endast ha en hänvisning 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 dubbelt länkade listor. Detta kan göra att flytta igenom enLista 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 fler referenser till andra noder i listan. Detta skapar en struktur liknandetill ett träd med hela grenar av noder som gytes från en enda. Dessa typer av datastrukturer kallas multiplicerade länkade listor. Multiplicerade länkade listor är särskilt användbara för komplexa sorteringsalgoritmer som används för att strukturera data.Sökträd är möjliga till stor del på grund av användning av länkade datastrukturer för att skapa flera grenar med variabel längd.