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å listan med en hänvisning till minnesadressen till den efterföljande noden. Länkade datastrukturer används i stället för en matris när numret på noder på en lista är okänd eller kan växa eller göra det för den exekverade datastrukturen. kallas en länkad lista.

En nod av en länkad datastruktur innehåller vanligtvis två bitar av information - en hänvisning till de faktiska data 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 datainstötarna, som börjar vid den första, eller huvudet på listan. slut.

mest länkad datastrukturES kommer att använda så lite minne som möjligt under programutförande. Om en länkad lista skapas med endast en nod och inga andra noder läggs till, kommer den listan att ta upp minnet 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 kan inte ändras.

Länkade listor betalar för deras effektiva användning av minnesresurser genom att kräva mer datorkraft. Att hitta en specifik databit i en länkad lista kräver looping genom hela listan varje gång, så det kan vara långsammare att få åtkomst till information i mitten av listan. Att ta bort eller omordna data i en länkad lista kan också vara mer beräkningsintensivt än att hantera en matris i vilken val av listan.

En länkad datastruktur krävs inte bara en referenstill nästa nod; Det kan ha flera. Vissa länkade listor har två nodreferenser, en till nästa nod i listan och en till den föregående noden. Dessa är kända som dubbelt länkade listor. Detta kan göra att flytta genom 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 fler referenser till andra noder i listan. Detta skapar en struktur som liknar ett träd med hela grenar av noder som skakar 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 sortering av algoritmer som används till strukturdata. grenar.