Vad är en cirkulär länkad lista?
En cirkulär länkad lista är en sekvens av noder ordnade så att varje nod kan återföras till sig själv. Här är en "nod" ett självreferenselement med pekare till en eller två noder i iIs omedelbara närhet.
Nedan är en bild av en cirkulär länkad lista med 3 noder.
Här kan du se att varje nod är återdragbar för sig själv. Exemplet som visas ovan är en cirkulär separat länkad lista.
Obs! Den mest enkla cirkulära länkade listan är en nod som bara spårar sig själv som visas
I denna cirkulär länkade handledning lär du dig:
- Vad är en cirkulär länkad lista?
- Grundläggande funktioner
- Användning av insättning
- Radering
- Korsning av en cirkulär länkad lista
- Fördelar med cirkulär länkad lista
- Enskild länkad lista som en cirkulär länkad lista
- Tillämpningar från den cirkulära länkade listan
Grundläggande funktioner
De grundläggande åtgärderna på en cirkulär länkad lista är:
- Införande
- Radering och
- Traversal
- Införande är processen att placera en nod på en viss position i den cirkulära länkade listan.
- Radering är processen att ta bort en befintlig nod från den länkade listan. Noden kan identifieras genom förekomsten av dess värde eller genom dess position.
- Korsning av en cirkulär länkad lista är processen att visa hela länkade listans innehåll och återgå till källnoden.
I nästa avsnitt kommer du att förstå insättning av en nod och vilka typer av insättning som är möjliga i en cirkulär singelinkad lista.
Användning av insättning
Inledningsvis måste du skapa en nod som pekar på sig själv som visas i den här bilden. Utan denna nod skapar insättning den första noden.
Därefter finns det två möjligheter:
- Infogning på den aktuella positionen i den cirkulära länkade listan. Detta motsvarar infogning i början av slutet av en vanlig, länkad lista. I en cirkulär länkad lista är början och slutet desamma.
- Insättning efter en indexerad nod. Noden ska identifieras med ett indexnummer som motsvarar dess elementvärde.
För att infoga i början / slutet av den cirkulära länkade listan, det vill säga på den plats där den första noden tillkom,
- Du måste bryta den befintliga självlänken till den befintliga noden
- Den nya nodens nästa pekare kommer att länka till den befintliga noden.
- Den sista nodens nästa pekare pekar på den infogade noden.
OBS: Pekaren som är tokenmastern eller början / slutet av cirkeln kan ändras. Det kommer fortfarande att återvända till samma nod på en genomgång, diskuterad framåt.
Stegen i (a) i-iii visas nedan:
(Befintlig nod)
STEG 1) Bryt den befintliga länken
STEG 2) Skapa en framåtlänk (från ny nod till en befintlig nod)
STEG 3) Skapa en slinglänk till den första noden
Därefter försöker du infoga efter en nod.
Låt oss till exempel infoga "VALUE2" efter noden med "VALUE0". Låt oss anta att startpunkten är noden med "VALUE0".
- Du måste bryta linjen mellan den första och andra noden och placera noden med "VALUE2" däremellan.
- Den första nodens nästa pekare måste länka till denna nod, och den här nodens nästa pekare måste länka till den tidigare andra noden.
- Resten av arrangemanget förblir oförändrat. Alla noder är återdragbara för sig själva.
OBS: Eftersom det finns ett cykliskt arrangemang innebär att infoga en nod samma procedur för vilken nod som helst. Pekaren som slutför en cykel slutför cykeln precis som alla andra noder.
Detta visas nedan:
(Låt oss säga att det bara finns två noder. Detta är ett trivialt fall)
STEG 1) Ta bort den inre länken mellan de anslutna noderna
STEG 2) Anslut noden till vänster till den nya noden
STEG 3) Anslut den nya noden till högernoden.
Radering
Låt oss anta en cirkellänkad lista med tre noder. Fallen för radering ges nedan:
- Ta bort det aktuella elementet
- Radering efter ett element.
Radering i början / slutet:
- Korsa till den första noden från den sista noden.
- För att ta bort från slutet bör det bara finnas ett traversalsteg, från den sista noden till den första noden.
- Ta bort länken mellan den sista noden och nästa nod.
- Länka den sista noden till nästa element i den första noden.
- Frigör den första noden.
(Befintlig installation)
STEG 1 ) Ta bort den cirkulära länken
STEG 2) Ta bort länken mellan första och nästa, länk den sista noden, till noden som följer den första
STEG 3) Frigör / dela den första noden
Radering efter en nod:
- Gå fram till nästa nod är den nod som ska raderas.
- Korsa till nästa nod, placera en pekare på föregående nod.
- Anslut den tidigare noden till noden efter den nuvarande noden med hjälp av nästa pekare.
- Frigör den nuvarande (avmarkerade) noden.
STEG 1) Låt oss säga att vi måste ta bort en nod med "VALUE1".
STEG 2) Ta bort länken mellan den föregående noden och den aktuella noden. Länka dess tidigare nod med nästa nod som pekas av den aktuella noden (med VALUE1).
STEG 3) Frigör eller återplacera den aktuella noden.
Korsning av en cirkulär länkad lista
För att korsa en cirkulär länkad lista, med början från en sista pekare, kontrollera om den sista pekaren är NULL. Om detta villkor är falskt, kontrollera om det bara finns ett element. Annars kan du korsa med en tillfällig pekare tills den sista pekaren nås igen, eller så många gånger som behövs, som visas i GIF nedan.
Fördelar med cirkulär länkad lista
Några av fördelarna med cirkulära länkade listor är:
- Inget krav på en NULL-uppgift i koden. Den cirkulära listan pekar aldrig på en NULL-pekare såvida den inte är helt omplacerad.
- Cirkulärt länkade listor är fördelaktiga för slutoperationer sedan början och slutet sammanfaller. Algoritmer som schemaläggningen Round Robin kan på ett enkelt sätt eliminera processer som är köade på ett cirkulärt sätt utan att stöta på dinglande eller NULL-referenspekare.
- Cirkulär länkad lista utför också alla vanliga funktioner i en enstaka länkad lista. Faktum är att cirkulära dubbelt länkade listor som diskuteras nedan kan till och med eliminera behovet av en längdkorsning för att lokalisera ett element. Det elementet skulle högst bara vara motsatt början och fylla bara hälften av den länkade listan.
Enskilt länkad lista som en cirkulär länkad lista
Du uppmanas att försöka läsa och implementera koden nedan. Den presenterar pekaren aritmetik associerad med cirkulära länkade listor.
#include#include 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(){…
Förklaring av kod:
- De två första kodraderna är de nödvändiga inkluderade rubrikfilerna.
- Nästa avsnitt beskriver strukturen för varje självreferensnod. Den innehåller ett värde och en pekare av samma typ som strukturen.
- Varje struktur länkar upprepade gånger till strukturobjekt av samma typ.
- Det finns olika funktionsprototyper för:
- Lägga till ett element i en tom länkad lista
- Infoga vid den just nu spetsiga positionen i en cirkulär länkad lista.
- Infoga efter ett visst indexerat värde i den länkade listan.
- Ta bort / ta bort efter ett visst indexerat värde i den länkade listan.
- Tar bort på den just nu pekade positionen i en cirkulär länkad lista
- Den sista funktionen skriver ut varje element genom en cirkulär genomgång i vilket tillstånd som helst i den länkade listan.
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)
Förklaring av kod:
- För addEmpty-koden, tilldela en tom nod med malloc-funktionen.
- För den här noden placerar du data till temp-variabeln.
- Tilldela och länka den enda variabeln till tempvariabeln
- Återställ det sista elementet till huvud () / applikationskontext.
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;…
Förklaring av kod
- Om det inte finns något element att infoga bör du se till att lägga till en tom lista och returnera kontrollen.
- Skapa ett tillfälligt element att placera efter det aktuella elementet.
- Länk pekarna som visas.
- Returnera den sista pekaren som i föregående funktion.
… 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");…
Förklaring av kod:
- Om det inte finns något element i listan, ignorera data, lägg till det aktuella objektet som det sista objektet i listan och returkontrollen
- Se till att det finns en tidigare pekare som håller det senast genomkorsade resultatet för varje iteration i gör-medan-slingan.
- Först då kan nästa genomgång inträffa.
- Om data hittas, eller om temp når tillbaka till den sista pekaren, avslutas underhållet. Nästa kodavsnitt avgör vad som ska göras med artikeln.
… 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)…
Förklaring av kod:
- Om hela listan har passerats, men objektet inte hittas, visa ett "objekt hittades inte" -meddelande och returnera sedan kontrollen till den som ringer.
- Om det finns en nod och / eller noden ännu inte är den sista noden, skapa en ny nod.
- Länka den tidigare noden med den nya noden. Länka den aktuella noden med temp (traversal-variabeln).
- Detta säkerställer att elementet placeras efter en viss nod i den cirkulära länkade listan. Återgå till 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)
Förklaring av kod
- För att ta bort endast den sista (nuvarande) noden, kontrollera om listan är tom. Om det är så kan inget element tas bort.
- Tempvariabeln passerar bara en länk framåt.
- Länka den sista pekaren till pekaren efter den första.
- Frigör temppekaren. Den omplacerar den icke-länkade sista pekaren.
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");…
Förklaring av kod
- Som med föregående borttagningsfunktion, kontrollera om det inte finns något element. Om detta är sant kan inget element tas bort.
- Pekare tilldelas specifika positioner för att hitta det element som ska raderas.
- Pekarna är avancerade, varandra bakom varandra. (tidigare bakom temp)
- Processen fortsätter tills ett element hittas, eller nästa element dras tillbaka till den sista pekaren.
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;
Förklaring av programmet
- Om elementet hittades efter att ha passerat hela den länkade listan visas ett felmeddelande som säger att objektet inte hittades.
- Annars är elementet avmarkerat och frigört i steg 3 och 4.
- Den föregående pekaren är länkad till adressen som pekas som "nästa" av det element som ska raderas (temp).
- Temp-pekaren delas därför ut och frigörs.
… 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;}}
Förklaring av kod
- Kik eller genomkörning är inte möjlig om det inte behövs någon. Användaren måste allokera eller infoga en nod.
- Om det bara finns en nod finns det inget behov av att korsa, nodens innehåll kan skrivas ut och while-loop körs inte.
- Om det finns mer än en nod, så skriver temp ut allt objekt till det sista elementet.
- I det ögonblick det sista elementet uppnås, slingan avslutas och funktionen återgår till huvudfunktionen.
Tillämpningar från den cirkulära länkade listan
- Implementering av rundbordsplanering i systemprocesser och cirkulär schemaläggning i höghastighetsgrafik.
- Token ringer schemaläggning i datornätverk.
- Den används i bildskärmsenheter som butikskort som kräver kontinuerlig dataöverföring.