Länkad lista är en linjär datastruktur, där element inte lagras på en sammanhängande plats, utan de är länkade med hjälp av pekare. Länkad lista bildar en serie anslutna noder, där varje nod lagrar data och adressen till nästa nod.

Nodstruktur: En nod i en länkad lista består vanligtvis av två komponenter:
Data: Den innehåller det faktiska värdet eller data som är associerade med noden.
Nästa pekare: Den lagrar minnesadressen (referens) för nästa nod i sekvensen.
Huvud och svans: Den länkade listan nås via huvudnoden, som pekar på den första noden i listan. Den sista noden i listan pekar på NULL eller nullptr, vilket indikerar slutet på listan. Denna nod är känd som svansnoden.

Varför behövs länkad listdatastruktur?

Här är några fördelar med en länkad lista som listas nedan, det hjälper dig att förstå varför det är nödvändigt att veta.

• Dynamisk datastruktur: Storleken på minnet kan tilldelas eller avallokeras vid körning baserat på operationen infogning eller borttagning.
• Enkel insättning/radering: Infogning och radering av element är enklare än arrayer eftersom inga element behöver flyttas efter infogning och borttagning, bara adressen behövde uppdateras.
• Effektivt minnesanvändning: Som vi vet är länkad lista en dynamisk datastruktur storleken ökar eller minskar enligt kravet så detta undviker slöseri med minne.
• Genomförande: Olika avancerade datastrukturer kan implementeras med hjälp av en länkad lista som en stack, kö, graf, hashkartor, etc.

Exempel:

I ett system, om vi upprätthåller en sorterad lista med ID:n i ett array-id[] = [1000, 1010, 1050, 2000, 2040].

Om vi ​​vill infoga ett nytt ID 1005 måste vi för att behålla den sorterade ordningen flytta alla element efter 1000 (exklusive 1000).

Radering är också dyrt med arrayer tills om inte några speciella tekniker används. Till exempel, för att ta bort 1010 i id[], måste allt efter 1010 flyttas på grund av detta så mycket arbete som görs vilket påverkar effektiviteten i koden.

Typer av länkade listor :

Det finns huvudsakligen tre typer av länkade listor:

1. Enkellänkad lista
2. Dubbel länkad lista
3. Cirkulär länkad lista

1. Enkellänkad lista :

I en enkellänkad lista innehåller varje nod en referens till nästa nod i sekvensen. Att gå igenom en enkellänkad lista görs i riktning framåt.

Enkellänkad lista

2. Dubbellänkad lista :

I en dubbellänkad lista innehåller varje nod referenser till både nästa och föregående noder. Detta möjliggör förflyttning både framåt och bakåt, men det kräver ytterligare minne för bakåtreferensen.

Dubbellänkad lista

3. Cirkulär länkad lista :

I en cirkulär länkad lista pekar den sista noden tillbaka till huvudnoden, vilket skapar en cirkulär struktur. Det kan vara antingen enskilt eller dubbelt länkat.

typskrift för varje

Cirkulär länkad lista

Operationer på länkade listor

1. Införande : Att lägga till en ny nod till en länkad lista innebär att man justerar pekarna för de befintliga noderna för att bibehålla rätt sekvens. Infogning kan utföras i början, slutet eller valfri position i listan
2. Radering : Att ta bort en nod från en länkad lista kräver justering av pekarna för de närliggande noderna för att överbrygga gapet som lämnas av den borttagna noden. Radering kan utföras i början, slutet eller valfri position i listan.
3. Sökande : Att söka efter ett specifikt värde i en länkad lista innebär att man går igenom listan från huvudnoden tills värdet hittas eller slutet av listan nås.

Komplexitetsanalys av länkad lista :

• Tidskomplexitet: O(n)
• Hjälputrymme: O(n)

Fördelar med länkade listor

• Dynamisk storlek: Länkade listor kan växa eller krympa dynamiskt, eftersom minnesallokering görs under körning.
• Insättning och radering: Att lägga till eller ta bort element från en länkad lista är effektivt, särskilt för stora listor.
• Flexibilitet: Länkade listor kan enkelt omorganiseras och modifieras utan att det krävs ett sammanhängande minnesblock.

Nackdelar med länkade listor

• Slumpmässig tillgång: Till skillnad från arrayer tillåter länkade listor inte direkt åtkomst till element via index. Traversering krävs för att nå en specifik nod.
• Extra minne: Länkade listor kräver ytterligare minne för att lagra pekarna, jämfört med arrayer.

Slutsats:

Länkade listor är mångsidiga datastrukturer som ger dynamisk minnesallokering och effektiva insättnings- och raderingsoperationer. Att förstå grunderna för länkade listor är viktigt för alla programmerare eller datavetenskapsentusiaster. Med denna kunskap kan du implementera länkade listor för att lösa olika problem och utöka din förståelse för datastrukturer och algoritmer.