Cirkulär länkad lista: Fördelar och nackdelar
Sarah Chen
Vad är en cirkulär länkad lista?
En cirkulär länkad lista är en sekvens av noder arrangerade på ett sådant sätt att varje nod kan spåras till sig själv. Här är en "nod" ett självreferenselement med pekare till en eller två noder i dess omedelbara närhet.
Nedan är en skildring av en cirkulär länkad lista med 3 noder.
Här kan du se att varje nod är spårbar till sig själv. Exemplet som visas ovan är en cirkulär enkellänkad lista.
Notera: Den enklaste cirkulära länkade listan är en nod som bara spårar sig själv som visas
Grundläggande Operationer i Circular Linked lists
De grundläggande funktionerna på en cirkulär länkad lista är:
- Införande
- Radering och
- Traversal
- Insättning är processen att placera en nod på en specificerad position i den cirkulärt länkade listan.
- Borttagning ä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.
- Genomgång av en cirkulär länkad lista är processen att visa hela den länkade listans innehåll och gå tillbaka till källnoden.
I nästa avsnitt kommer du att förstå infogning av en nod och vilka typer av infogning som är möjliga i en cirkulär enkellänkad lista.
Införande Operation
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 för den cirkulära länkade listan. Detta motsvarar infogning i början av slutet av en vanlig singular länkad lista. I en cirkulär länkad lista är början och slutet desamma.
- Infogning 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 position där den första noden någonsin lades till,
- 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 kommer att peka på den infogade noden.
OBS: Pekaren som är tokenmastern eller början/slutet av cirkeln kan ändras. Den kommer fortfarande att återgå till samma nod vid en genomgång, diskuterad i förväg.
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 looplänk till den första noden
Därefter kommer du att försöka 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" emellan.
- 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 spårbara till 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 fullbordar cykeln precis som vilken annan nod som helst.
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 den vänstra noden till den nya noden
STEG 3) Anslut den nya noden till den högra noden.
deletion Operation
Låt oss anta en cirkulär länkad lista med 3 noder. Fallen för radering anges nedan:
- Ta bort det aktuella elementet
- Radering efter ett element.
Radering i början/slutet:
- Gå till den första noden från den sista noden.
- För att radera från slutet bör det bara finnas ett genomgångssteg, 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 inställning)
STEG 1) Ta bort den cirkulära länken
STEG 2) Ta bort länken mellan den första och nästa, länka den sista noden, till noden efter den första
STEG 3) Frigör / deallokera den första noden
Radering efter en nod:
- Gå tills nästa nod är den nod som ska raderas.
- Gå till nästa nod, placera en pekare på föregående nod.
- Anslut den föregående noden till noden efter den nuvarande noden med hjälp av dess nästa pekare.
- Frigör den nuvarande (bortkopplade) 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 föregående nod och nuvarande nod. Länka dess föregående nod med nästa nod som pekas av den aktuella noden (med VALUE1).
STEG 3) Frigör eller avallokera den aktuella noden.
Genomgång av en cirkulär länkad lista
För att gå igenom en cirkulär länkad lista, med början från en sista pekare, kontrollera om den sista pekaren i sig är NULL. Om detta villkor är falskt, kontrollera om det bara finns ett element. I annat fall, gå genom att använda 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 Circular Linked List
Några av fördelarna med cirkulärt länkade listor är:
- Inget krav på NULL-uppdrag i koden. Den cirkulära listan pekar aldrig på en NULL-pekare om den inte är helt avallokerad.
- Cirkulärt länkade listor är fördelaktiga för slutoperationer eftersom början och slutet sammanfaller. Algorithms t.ex. Round Robin-schemaläggningen kan prydligt 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 enkellänkad lista. Faktiskt cirkulär dubbelt länkade listor som diskuteras nedan kan till och med eliminera behovet av en genomgång i full längd för att lokalisera ett element. Det elementet skulle på sin höjd bara vara precis motsatt start och bara fylla halva den länkade listan.
Nackdelar med Circular Linked List
Nackdelarna med att använda en cirkulär länkad lista är nedan:
- Cirkulära listor är komplexa jämfört med enbart länkade listor.
- RevErse av cirkulär lista är ett komplex jämfört med enstaka eller dubbla listor.
- Om den inte hanteras försiktigt kan koden gå i en oändlig loop.
- Svårare att hitta slutet av listan och loopkontroll.
- När vi infogar vid Start måste vi gå igenom hela listan för att hitta den sista noden. (Implementeringsperspektiv)
Enkelt länkad lista som en cirkulär länkad lista
Du uppmuntras att försöka läsa och implementera koden nedan. Den presenterar pekarritmetiken förknippad med cirkulärt länkade listor.
#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()
{
...
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
- Insättning vid för närvarande pekade positionen för en cirkulär länkad lista.
- Infoga efter en viss indexeras värde i den länkade listan.
- Ta bort/ta bort efter en viss indexeras värde i den länkade listan.
- Ta bort på den för närvarande pekade positionen av en cirkulär länkad lista
- Den sista funktionen skriver ut varje element genom en cirkulär korsning i vilket läge 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, allokera en tom nod med malloc-funktionen.
- För denna nod, placera data till tempvariabeln.
- Tilldela och länka den enda variabeln till tempvariabeln
- Returnera det sista elementet till main()/applikationskontexten.
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 i en tom lista och returnera kontroll.
- Skapa ett tillfälligt element att placera efter det aktuella elementet.
- Länka pekarna enligt bilden.
- 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 returnera kontroll
- För varje iteration i do-while-loopen, se till att det finns en tidigare pekare som håller det senast korsade resultatet.
- Först då kan nästa traversering ske.
- Om data hittas, eller temp når tillbaka till den sista pekaren, avslutas do-while. Nästa avsnitt av koden bestämmer vad som ska göras med objektet.
...
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 återför 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änk den föregående noden med den nya noden. Länka den aktuella noden med temp (traversalvariabeln).
- 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 bara ta bort den sista (nuvarande) noden, kontrollera om den här listan är tom. Om så är fallet kan inget element tas bort.
- Temperaturvariabeln går bara en länk framåt.
- Länka den sista pekaren till pekaren efter den första.
- Frigör temppekaren. Den avallokerar den olä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 den tidigare borttagningsfunktionen, kontrollera om det inte finns något element. Om detta är sant kan inget element tas bort.
- Pekare tilldelas specifika positioner för att lokalisera elementet som ska raderas.
- Pekarna flyttas fram, den ena bakom den andra. (föregående bakom temp)
- Processen fortsätter tills ett element hittas, eller tills nästa element går 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 hittas efter att ha gått igenom hela den länkade listan, visas ett felmeddelande som säger att objektet inte hittades.
- Annars kopplas elementet bort och frigörs i steg 3 och 4.
- Den föregående pekaren är länkad till adressen som pekas som "nästa" av elementet som ska raderas (temp).
- Temp-pekaren är därför avallokerad 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
- Titta eller korsning är inte möjlig om det behövs noll. 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-loopen körs inte.
- Om det finns mer än en nod, skriver tempen ut hela objektet till det sista elementet.
- I det ögonblick det sista elementet nås avslutas loopen och funktionen returnerar anrop till huvudfunktionen.
Tillämpningar av den cirkulära länkade listan
- Implementera round-robin schemaläggning i systemprocesser och cirkulär schemaläggning i höghastighetsgrafik.
- Token ringer schemaläggning i datornätverk.
- Det används i displayenheter som butikstavlor som kräver kontinuerlig övergång av data.
