Linket liste er en lineær datastruktur, hvor elementer ikke er gemt på et sammenhængende sted, men de er forbundet ved hjælp af pointere. Linked List danner en serie af forbundne noder, hvor hver node gemmer dataene og adressen på den næste node.
Nodestruktur: En node i en sammenkædet liste består typisk af to komponenter:
Data: Den indeholder den faktiske værdi eller data, der er knyttet til noden.
Næste pointer: Den gemmer hukommelsesadressen (referencen) for den næste node i sekvensen.
Hoved og hale: Den sammenkædede liste tilgås gennem hovedknuden, som peger på den første knude på listen. Den sidste node på listen peger på NULL eller nullptr, hvilket indikerer slutningen af listen. Denne knude er kendt som haleknuden.
Hvorfor er linket listedatastruktur nødvendig?
Her er et par fordele ved en linket liste, der er angivet nedenfor, det vil hjælpe dig med at forstå, hvorfor det er nødvendigt at vide.
- Dynamisk datastruktur: Størrelsen af hukommelsen kan tildeles eller deallokeres på køretid baseret på operationens indsættelse eller sletning.
- Nem indsættelse/sletning: Indsættelse og sletning af elementer er enklere end arrays, da ingen elementer skal flyttes efter indsættelse og sletning, kun adressen skal opdateres.
- Effektiv hukommelsesudnyttelse: Som vi ved, er Linked List en dynamisk datastruktur, størrelsen stiger eller falder i henhold til kravet, så dette undgår spild af hukommelse.
- Implementering: Forskellige avancerede datastrukturer kan implementeres ved hjælp af en linket liste som en stak, kø, graf, hash-kort osv.
Eksempel:
I et system, hvis vi opretholder en sorteret liste over ID'er i et array-id[] = [1000, 1010, 1050, 2000, 2040].
Hvis vi ønsker at indsætte et nyt ID 1005, så skal vi flytte alle elementerne efter 1000 for at bevare den sorterede rækkefølge (eksklusive 1000).
Sletning er også dyrt med arrays indtil, medmindre der bruges nogle specielle teknikker. For eksempel, for at slette 1010 i id[], skal alt efter 1010 flyttes på grund af dette, der bliver gjort så meget arbejde, som påvirker effektiviteten af koden.
Typer af linkede lister :
Der er hovedsageligt tre typer af linkede lister:
- Enkelt-linket liste
- Dobbelt linket liste
- Cirkulær linket liste
1. Enkelt-linket liste :
I en enkelt linket liste indeholder hver node en reference til den næste node i sekvensen. Gennemgang af en enkelt-linket liste sker i en fremadgående retning.
Enkeltforbundet liste
2. Dobbelt-linket liste :
I en dobbelt linket liste indeholder hver node referencer til både den næste og forrige node. Dette giver mulighed for traversering i både fremadgående og bagudgående retninger, men det kræver yderligere hukommelse til baglænsreferencen.
Dobbelt-linket liste
3. Cirkulær linket liste :
I en cirkulær sammenkædet liste peger den sidste node tilbage til hovedknuden, hvilket skaber en cirkulær struktur. Det kan enten være enkelt- eller dobbeltforbundet.
java synkronisering
Cirkulær linket liste
Operationer på linkede lister
- Indskud : Tilføjelse af en ny node til en sammenkædet liste indebærer justering af pointerne for de eksisterende noder for at opretholde den korrekte rækkefølge. Indsættelse kan udføres ved begyndelsen, slutningen eller en hvilken som helst position på listen
- Sletning : Fjernelse af en node fra en sammenkædet liste kræver justering af pointerne på de tilstødende noder for at bygge bro over det mellemrum, som den slettede node efterlader. Sletning kan udføres ved begyndelsen, slutningen eller en hvilken som helst position på listen.
- Søger : Søgning efter en specifik værdi i en sammenkædet liste involverer at krydse listen fra hovedknuden, indtil værdien er fundet, eller slutningen af listen er nået.
Kompleksitetsanalyse af linket liste :
- Tidskompleksitet: O(n)
- Hjælpeplads: O(n)
Fordele ved linkede lister
- Dynamisk størrelse: Sammenkædede lister kan vokse eller formindskes dynamisk, da hukommelsesallokering udføres under kørsel.
- Indsættelse og sletning: Tilføjelse eller fjernelse af elementer fra en sammenkædet liste er effektivt, især for store lister.
- Fleksibilitet: Sammenkædede lister kan nemt omorganiseres og ændres uden at kræve en sammenhængende hukommelsesblok.
Ulemper ved linkede lister
- Tilfældig adgang: I modsætning til arrays tillader linkede lister ikke direkte adgang til elementer efter indeks. Traversering er påkrævet for at nå en bestemt knude.
- Ekstra hukommelse: Sammenkædede lister kræver ekstra hukommelse til lagring af pointere sammenlignet med arrays.
Konklusion:
Sammenkædede lister er alsidige datastrukturer, der giver dynamisk hukommelsesallokering og effektive indsættelses- og sletningsoperationer. At forstå det grundlæggende i linkede lister er afgørende for enhver programmør eller datalogientusiast. Med denne viden kan du implementere linkede lister til at løse forskellige problemer og udvide din forståelse af datastrukturer og algoritmer.