Koblet liste er en lineær datastruktur, der elementer ikke er lagret på et sammenhengende sted, men de er koblet sammen ved hjelp av pekere. Linked List danner en serie med tilkoblede noder, der hver node lagrer dataene og adressen til neste node.

Nodestruktur: En node i en koblet liste består vanligvis av to komponenter:
Data: Den inneholder den faktiske verdien eller dataene knyttet til noden.
Neste peker: Den lagrer minneadressen (referansen) til neste node i sekvensen.
Hode og hale: Den koblede listen er tilgjengelig via hodenoden, som peker til den første noden i listen. Den siste noden i listen peker på NULL eller nullptr, som indikerer slutten av listen. Denne noden er kjent som haleknuten.

Hvorfor er det nødvendig med lenket listedatastruktur?

Her er noen fordeler med en koblet liste som er oppført nedenfor, det vil hjelpe deg å forstå hvorfor det er nødvendig å vite.

• Dynamisk datastruktur: Størrelsen på minnet kan tildeles eller deallokeres på kjøretid basert på operasjonen innsetting eller sletting.
• Enkel innsetting/sletting: Innsetting og sletting av elementer er enklere enn arrays siden ingen elementer må flyttes etter innsetting og sletting, bare adressen må oppdateres.
• Effektiv minneutnyttelse: Som vi vet er Linked List en dynamisk datastruktur, størrelsen øker eller reduseres i henhold til kravet, slik at dette unngår sløsing med minne.
• Gjennomføring: Ulike avanserte datastrukturer kan implementeres ved hjelp av en koblet liste som en stabel, kø, graf, hash-kart, etc.

Eksempel:

I et system, hvis vi opprettholder en sortert liste over IDer i en matrise-id[] = [1000, 1010, 1050, 2000, 2040].

Hvis vi ønsker å sette inn en ny ID 1005, må vi flytte alle elementene etter 1000 for å opprettholde den sorterte rekkefølgen (unntatt 1000).

Sletting er også dyrt med arrays inntil med mindre noen spesielle teknikker brukes. For å for eksempel slette 1010 i id[], må alt etter 1010 flyttes på grunn av dette så mye arbeid som blir gjort som påvirker effektiviteten til koden.

Typer koblede lister :

Det er hovedsakelig tre typer koblede lister:

1. Enkeltlenket liste
2. Dobbel lenket liste
3. Sirkulær lenket liste

1. Enkeltlenket liste :

I en enkeltlenket liste inneholder hver node en referanse til neste node i sekvensen. Å krysse en enkeltlenket liste gjøres i retning fremover.

Enkeltlenket liste

2. Dobbeltlenket liste :

I en dobbeltlenket liste inneholder hver node referanser til både neste og forrige noder. Dette tillater traversering både fremover og bakover, men det krever ekstra minne for bakoverreferansen.

Dobbeltlenket liste

3. Sirkulær lenket liste :

I en sirkulær koblet liste peker den siste noden tilbake til hodenoden, og skaper en sirkulær struktur. Det kan enten være enkelt- eller dobbeltkoblet.

java slutten

Sirkulær lenket liste

Operasjoner på koblede lister

1. Innsetting : Å legge til en ny node til en koblet liste innebærer å justere pekerne til de eksisterende nodene for å opprettholde riktig sekvens. Innsetting kan utføres på begynnelsen, slutten eller en hvilken som helst plassering i listen
2. Sletting : Å fjerne en node fra en koblet liste krever justering av pekerne til nabonodene for å bygge bro over gapet som er igjen av den slettede noden. Sletting kan utføres på begynnelsen, slutten eller en hvilken som helst plassering i listen.
3. Søker : Å søke etter en bestemt verdi i en koblet liste innebærer å gå gjennom listen fra hodenoden til verdien er funnet eller slutten av listen er nådd.

Kompleksitetsanalyse av koblet liste :

• Tidskompleksitet: O(n)
• Hjelpeområde: O(n)

Fordeler med koblede lister

• Dynamisk størrelse: Koblede lister kan vokse eller krympe dynamisk, ettersom minnetildeling gjøres under kjøring.
• Innsetting og sletting: Å legge til eller fjerne elementer fra en koblet liste er effektivt, spesielt for store lister.
• Fleksibilitet: Koblede lister kan enkelt omorganiseres og endres uten å kreve en sammenhengende minneblokk.

Ulemper med koblede lister

• Tilfeldig tilgang: I motsetning til matriser, tillater ikke koblede lister direkte tilgang til elementer etter indeks. Traversering er nødvendig for å nå en bestemt node.
• Ekstra minne: Koblede lister krever ekstra minne for lagring av pekere, sammenlignet med matriser.

Konklusjon:

Koblede lister er allsidige datastrukturer som gir dynamisk minneallokering og effektive innsettings- og slettingsoperasjoner. Å forstå det grunnleggende om koblede lister er avgjørende for enhver programmerer eller informatikkentusiast. Med denne kunnskapen kan du implementere koblede lister for å løse ulike problemer og utvide din forståelse av datastrukturer og algoritmer.