Sirkulær lenket liste: fordeler og ulemper
Hva er en sirkulær lenket liste?
En sirkulær koblet liste er en sekvens av noder arrangert slik at hver node kan spores tilbake til seg selv. Her er en "node" et selvrefererende element med pekere til en eller to noder i umiddelbar nærhet.
Nedenfor er en skildring av en sirkulær koblet liste med 3 noder.
Her kan du se at hver node er sporbar til seg selv. Eksemplet vist ovenfor er en sirkulær enkeltlenket liste.
Merk: Den enkleste sirkulære lenkede listen er en node som sporer kun til seg selv som vist
Basic Operasjoner i Circular Linked-lister
De grunnleggende operasjonene på en sirkulær koblet liste er:
- Innsetting
- Sletting og
- traversering
- Innsetting er prosessen med å plassere en node på en spesifisert posisjon i den sirkulære lenkede listen.
- Sletting er prosessen med å fjerne en eksisterende node fra den koblede listen. Noden kan identifiseres ved forekomsten av dens verdi eller ved dens posisjon.
- Gjennomgang av en sirkulær lenket liste er prosessen med å vise hele den lenkede listens innhold og gå tilbake til kildenoden.
I neste avsnitt vil du forstå innsetting av en node, og hvilke typer innsetting som er mulig i en sirkulær enkeltlenket liste.
Innsetting Operasjon
Til å begynne med må du lage en node som peker til seg selv som vist i dette bildet. Uten denne noden skaper innsetting den første noden.
Deretter er det to muligheter:
- Innsetting på gjeldende plassering av den sirkulære lenkede listen. Dette tilsvarer innsetting på begynnelsen av slutten av en vanlig singular lenket liste. I en sirkulær lenket liste er begynnelsen og slutten den samme.
- Innsetting etter en indeksert node. Noden skal identifiseres med et indeksnummer som tilsvarer elementverdien.
For å sette inn på begynnelsen/slutten av den sirkulære lenkede listen, det vil si på posisjonen der den første noden noensinne ble lagt til,
- Du må bryte den eksisterende selvkoblingen til den eksisterende noden
- Den nye nodens neste peker vil koble til den eksisterende noden.
- Den siste nodens neste peker vil peke på den innsatte noden.
MERK: Pekeren som er token master eller begynnelsen/slutten av sirkelen kan endres. Den vil fortsatt gå tilbake til den samme noden på en traversering, diskutert fremover.
Trinn i (a) i-iii er vist nedenfor:
(Eksisterende node)
TRINN 1) Bryt den eksisterende koblingen
TRINN 2) Opprett en viderekobling (fra ny node til en eksisterende node)
TRINN 3) Lag en sløyfekobling til den første noden
Deretter vil du prøve å sette inn etter en node.
La oss for eksempel sette inn "VALUE2" etter noden med "VALUE0". La oss anta at utgangspunktet er noden med "VALUE0".
- Du må bryte linjen mellom første og andre node og plassere noden med "VALUE2" i mellom.
- Den første nodens neste peker må kobles til denne noden, og denne nodens neste peker må kobles til den tidligere andre noden.
- Resten av ordningen forblir uendret. Alle noder er sporbare til seg selv.
MERK: Siden det er et syklisk arrangement, innebærer å sette inn en node samme prosedyre for enhver node. Pekeren som fullfører en syklus, fullfører syklusen akkurat som alle andre noder.
Dette er vist nedenfor:
(La oss si at det bare er to noder. Dette er en triviell sak)
TRINN 1) Fjern den indre koblingen mellom de tilkoblede nodene
TRINN 2) Koble noden på venstre side til den nye noden
TRINN 3) Koble den nye noden til noden på høyre side.
sletting Operasjon
La oss anta en sirkulær lenket liste med 3 noder. Sakene for sletting er gitt nedenfor:
- Sletter gjeldende element
- Sletting etter et element.
Sletting i begynnelsen/slutt:
- Gå til den første noden fra den siste noden.
- For å slette fra slutten, bør det bare være ett traverseringstrinn, fra siste node til første node.
- Slett koblingen mellom siste node og neste node.
- Koble den siste noden til neste element i den første noden.
- Frigjør den første noden.
(Eksisterende oppsett)
TRINN 1) Fjern den sirkulære lenken
TRINN 2) Fjern koblingen mellom den første og neste, koble den siste noden, til noden etter den første
TRINN 3) Frigjør / dealloker den første noden
Sletting etter en node:
- Gå til neste node er noden som skal slettes.
- Gå til neste node, plasser en peker på forrige node.
- Koble den forrige noden til noden etter den nåværende noden ved å bruke dens neste peker.
- Frigjør den nåværende (frakoblede) noden.
TRINN 1) La oss si at vi må slette en node med "VALUE1."
TRINN 2) Fjern koblingen mellom forrige node og gjeldende node. Koble den forrige noden til den neste noden pekt av gjeldende node (med VALUE1).
TRINN 3) Frigjør eller fjern allokering av gjeldende node.
Gjennomgang av en sirkulær lenket liste
For å gå gjennom en sirkulær lenket liste, start fra en siste peker, sjekk om den siste pekeren i seg selv er NULL. Hvis denne betingelsen er usann, sjekk om det bare er ett element. Ellers kan du gå gjennom en midlertidig peker til den siste pekeren nås igjen, eller så mange ganger som nødvendig, som vist i GIF-en nedenfor.
Fordeler med Circular Linked List
Noen av fordelene med sirkulære lenkede lister er:
- Ingen krav om NULL-oppgave i koden. Den sirkulære listen peker aldri til en NULL-peker med mindre den er fullstendig deallokert.
- Sirkulære lenkede lister er fordelaktige for sluttoperasjoner siden begynnelsen og slutten faller sammen. Algorithms slik som Round Robin-planleggingen kan eliminere prosesser som er i kø på en sirkulær måte uten å møte dinglende eller NULL-referansepekere.
- Sirkulær koblet liste utfører også alle vanlige funksjoner til en enkeltlenket liste. Faktisk sirkulær dobbeltkoblede lister diskutert nedenfor kan til og med eliminere behovet for en full-lengde traversering for å lokalisere et element. Det elementet ville på det meste bare være nøyaktig motsatt av starten, og fullføre bare halvparten av den koblede listen.
Ulemper med Circular Linked List
Ulempene ved å bruke en sirkulær lenket liste er nedenfor:
- Sirkulære lister er komplekse sammenlignet med enkeltlenkede lister.
- RevErse av sirkulær liste er et kompleks sammenlignet med enkelt- eller dobbeltlister.
- Hvis den ikke håndteres forsiktig, kan koden gå i en uendelig sløyfe.
- Vanskeligere å finne slutten av listen og sløyfekontroll.
- Ved å sette inn ved Start, må vi gå gjennom hele listen for å finne den siste noden. (Implementeringsperspektiv)
Enkeltlenket liste som en sirkulær koblet liste
Du oppfordres til å prøve å lese og implementere koden nedenfor. Den presenterer peker-aritmetikken knyttet til sirkulære lenkede lister.
#include<stdio.h> #include<stdlib.h> struct node { int item; struct node *next; }; struct node* addToEmpty(struct node*,int); struct node *insertCurrent(struct node *, int); struct node *insertAfter(struct node *, int, int); struct node *removeAfter(struct node *, int); struct node *removeCurrent(struct node *); void peek(struct node *); int main() { ...
Forklaring av kode:
- De to første linjene med kode er de nødvendige inkluderte overskriftsfilene.
- Den neste delen beskriver strukturen til hver selvrefererende node. Den inneholder en verdi og en peker av samme type som strukturen.
- Hver struktur lenker gjentatte ganger til strukturobjekter av samme type.
- Det finnes forskjellige funksjonsprototyper for:
- Legge til et element i en tom lenket liste
- Setter inn ved for øyeblikket pekt plasseringen av en sirkulær lenket liste.
- Setter inn etter en bestemt indeksert verdi i den koblede listen.
- Fjerne/slette etter en bestemt indeksert verdi i den koblede listen.
- Fjerner ved den pekende posisjonen til en sirkulær lenket liste
- Den siste funksjonen skriver ut hvert element gjennom en sirkulær traversering i hvilken som helst tilstand av den koblede listen.
int main() { struct node *last = NULL; last = insertCurrent(last,4); last = removeAfter(last, 4); peek(last); return 0; } struct node* addToEmpty(struct node*last, int data) { struct node *temp = (struct node *)malloc(sizeof( struct node)); temp->item = data; last = temp; last->next = last; return last; } struct node *insertCurrent(struct node *last, int data)
Forklaring av kode:
- For addEmpty-koden, alloker en tom node ved hjelp av malloc-funksjonen.
- For denne noden, plasser dataene til temp-variabelen.
- Tilordne og koble den eneste variabelen til temp-variabelen
- Returner det siste elementet til main() / applikasjonskonteksten.
struct node *insertCurrent(struct node *last, int data) { if(last == NULL) { return addToEmpty(last, data); } struct node *temp = (struct node *)malloc(sizeof( struct node)); temp -> item = data; temp->next = last->next; last->next = temp; return last; } struct node *insertAfter(struct node *last, int data, int item) { struct node *temp = last->next, *prev = temp, *newnode =NULL; …
Forklaring av kode
- Hvis det ikke er noe element å sette inn, bør du sørge for å legge til en tom liste og returnere kontroll.
- Opprett et midlertidig element som skal plasseres etter det gjeldende elementet.
- Koble sammen pekerne som vist.
- Returner den siste pekeren som i forrige funksjon.
... struct node *insertAfter(struct node *last, int data, int item) { struct node *temp = last->next, *prev = temp, *newnode =NULL; if (last == NULL) { return addToEmpty(last, item); } do { prev = temp; temp = temp->next; } while (temp->next != last && temp->item != data ); if(temp->item != data) { printf("Element not found. Please try again"); ...
Forklaring av kode:
- Hvis det ikke er noe element i listen, ignorer dataene, legg til gjeldende element som siste element i listen og returner kontroll
- For hver iterasjon i do-while-løkken, sørg for at det er en tidligere peker som holder det sist gjennomkjørte resultatet.
- Først da kan neste traversering skje.
- Hvis dataene blir funnet, eller temperaturen når tilbake til den siste pekeren, avsluttes do-while. Den neste delen av koden bestemmer hva som skal gjøres med elementet.
... if(temp->item != data) { printf("Element not found. Please try again"); return last; } else { newnode = (struct node *)malloc(sizeof(struct node)); newnode->item = item; prev->next = newnode; newnode->next = temp; } return last; } struct node *removeCurrent(struct node *last) ...
Forklaring av kode:
- Hvis hele listen har blitt krysset, men elementet ikke er funnet, vis en "element ikke funnet"-melding og returner deretter kontrollen til den som ringer.
- Hvis det er en node funnet, og/eller noden ennå ikke er den siste noden, oppretter du en ny node.
- link den forrige noden med den nye noden. Koble gjeldende node med temp (traversalvariabelen).
- Dette sikrer at elementet plasseres etter en bestemt node i den sirkulære lenkede listen. Gå tilbake til den som ringer.
struct node *removeCurrent(struct node *last) { if(last == NULL) { printf("Element Not Found"); return NULL; } struct node *temp = last->next; last->next = temp->next; free(temp); return last; } struct node *removeAfter(struct node *last, int data)
Forklaring av kode
- For å fjerne bare den siste (nåværende) noden, sjekk om denne listen er tom. Hvis det er det, kan ingen elementer fjernes.
- Temperaturvariabelen krysser bare én lenke fremover.
- Koble den siste pekeren til pekeren etter den første.
- Frigjør temppekeren. Den tildeler den siste pekeren som ikke er koblet til.
struct node *removeAfter(struct node *last,int data) { struct node *temp = NULL,*prev = NULL; if (last == NULL) { printf("Linked list empty. Cannot remove any element\n"); return NULL; } temp = last->next; prev = temp; do { prev = temp; temp = temp->next; } while (temp->next != last && temp->item != data ); if(temp->item != data) { printf("Element not found"); ...
Forklaring av kode
- Som med den forrige fjerningsfunksjonen, sjekk om det ikke er noe element. Hvis dette er sant, kan ingen elementer fjernes.
- pekere er tildelt spesifikke posisjoner for å finne elementet som skal slettes.
- Pekerne er avanserte, den ene bak den andre. (forrige bak temp)
- Prosessen fortsetter til et element er funnet, eller det neste elementet går tilbake til den siste pekeren.
if(temp->item != data) { printf("Element not found"); return last; } else { prev->next = temp->next; free(temp); } return last; } void peek(struct node * last) { struct node *temp = last; if (last == NULL) { return;
Forklaring av program
- Hvis elementet ble funnet etter å ha gått gjennom hele den koblede listen, vises en feilmelding som sier at elementet ikke ble funnet.
- Ellers blir elementet frakoblet og frigjort i trinn 3 og 4.
- Den forrige pekeren er knyttet til adressen pekt som "neste" av elementet som skal slettes (temp).
- Temp-pekeren er derfor deallokert og frigjort.
... void peek(struct node * last) { struct node *temp = last; if (last == NULL) { return; } if(last -> next == last) { printf("%d-", temp->item); } while (temp != last) { printf("%d-", temp->item); temp = temp->next; } }
Forklaring av kode
- Kikk eller kryssing er ikke mulig hvis det ikke er behov for null. Brukeren må tildele eller sette inn en node.
- Hvis det bare er én node, er det ikke nødvendig å krysse, nodens innhold kan skrives ut, og while-løkken kjøres ikke.
- Hvis det er mer enn én node, skriver vikaren ut hele elementet til det siste elementet.
- I øyeblikket når det siste elementet er nådd, avsluttes løkken, og funksjonen returnerer kall til hovedfunksjonen.
Anvendelser av den sirkulære lenkede listen
- Implementering av round-robin-planlegging i systemprosesser og sirkulær planlegging i høyhastighetsgrafikk.
- Token ringer planlegging i datanettverk.
- Den brukes i displayenheter som butikktavler som krever kontinuerlig gjennomgang av data.