Cirkulär länkad lista: Fördelar och nackdelar

Vad är en cirkulär länkad lista?

En cirkulär länkad lista är en sekvens av noder arrangerade så att varje nod kan återskapastraced till sig själv. Varje "nod" är ett självrefererande element med pekare till en eller två noder i sin 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 återställdtracmöjlig för sig själv. Exemplet som visas ovan är en cirkulär, enkellänkad lista.

Obs: Den enklaste cirkulära länkade listan är en enda nod vars nästa pekare traces tillbaka till sig själv, som visas nedan.

Grundläggande Operationer i cirkulära länkade listor

De tre grundläggande operationerna på en cirkulär länkad lista är:

1. Införande
2. Radering och
3. 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.
• Traversering av en cirkulär länkad lista är processen att visa hela den länkade listans innehåll och återskapa den.tractillbaka till källnoden.

Nästa avsnitt förklarar hur infogning fungerar och de två typerna av infogning som är möjliga i en cirkulär, enkellänkad lista.

Införande Operation

Du skapar först en nod vars nästa pekare pekar tillbaka till sig själv, som visas nedan. Utan denna frönod blir den första infogningen den första noden i listan.

Därefter finns det två möjligheter:

• Infogning vid den aktuella positionen för den cirkulärlänkade listan. Detta motsvarar infogning i antingen början eller slutet av en vanlig enkellänkad lista — i en cirkulärlänkad lista är början och slutet samma punkt.
• Infogning efter en indexerad nod. Noden ska identifieras med ett indexnummer som motsvarar dess elementvärde.

För att infoga i början eller slutet av den cirkulära länkade listan – det vill säga på den position där den allra första noden lades till – följ stegen nedan:

• 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 markerar början eller slutet av cirkeln kan tilldelas vilken nod som helst. En genomgång kommer fortfarande att återgå till samma nod, vilket diskuteras senare i den här artikeln.

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.

Till exempel, infoga ”VÄRDE2” efter noden som innehåller ”VÄRDE0”, förutsatt att startpunkten är noden med ”VÄRDE0”.

• Bryt länken mellan den första och andra noden och placera noden med "VALUE2" emellan.
• Den första nodens nästa pekare länkar till den nya noden, och den nya nodens nästa pekare länkar till det som tidigare var den andra noden.
• Resten av arrangemanget förblir oförändrat. Alla noder är återställda.tractillgängliga för sig själva.

OBS: Eftersom arrangemanget är cykliskt är proceduren för att infoga en nod identisk oavsett vilken position du väljer. Pekaren som avslutar cykeln beter sig som vilken annan pekare som helst i listan.

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

Antag en cirkulär länkad lista med 3 noder. De två borttagningsfallen är:

• Ta bort det aktuella elementet
• Radering efter ett element.

Radering i början/slutet:

1. Gå till den första noden från den sista noden.
2. Att ta bort från slutet kräver bara ett steg, från den sista noden till den första noden.
3. Ta bort länken mellan den sista noden och den första noden.
4. Länka den sista noden till nästa element i den första noden.
5. 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/avallokera den första noden

Radering efter en nod:

1. Gå igenom tills nästa nod är den nod som ska tas bort.
2. Gå till nästa nod, placera en pekare på föregående nod.
3. Anslut den föregående noden till noden efter den nuvarande noden med hjälp av dess nästa pekare.
4. 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 den föregående noden och den aktuella noden, länka sedan den föregående noden direkt till noden som den aktuella nodens nästa pekare pekar på (noden efter 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 från en sista pekare, kontrollera först om den sista pekaren är NULL. Om den inte är NULL, kontrollera om listan bara har ett element. Annars, gå igenom listan med en tillfällig pekare tills du når den sista pekaren igen, som visas i animationen nedan.

Fördelar med Circular Linked List

Några av fördelarna med cirkulärt länkade listor är:

1. Inget krav på NULL-uppdrag i koden. Den cirkulära listan pekar aldrig på en NULL-pekare om den inte är helt avallokerad.
2. Cirkulära länkade listor är fördelaktiga för operationer vid slutet av listan eftersom början och slutet sammanfaller. Algorithms såsom round-robin-schemaläggning kan röra sig igenom köade processer snyggt, utan att stöta på dinglande eller NULL-pekare.
3. En cirkulär länkad lista stöder fortfarande alla vanliga operationer i en enkellänkad lista. dubbelt länkad lista kan till och med eliminera behovet av en fulllängdsgenomgång för att lokalisera ett element – ​​i värsta fall sitter målet mittemot startpekaren, så högst halva listan behöver gås.

Nackdelar med Circular Linked List

Nackdelarna med att använda en cirkulär länkad lista är nedan:

1. Cirkulära listor är mer komplexa än enbart länkade listor.
2. RevAtt radera en cirkulär lista är mer komplext än att reversera en enkel- eller dubbellänkad lista.
3. Om loopavslutningen inte hanteras noggrant kan traversalkoden gå in i en oändlig loop.
4. Det är svårare att hitta slutet på listan och att skriva korrekta loopkontrollvillkor.
5. Att infoga i början kräver att man går igenom hela listan för att nå den sista noden (ur ett implementeringsperspektiv).

Enkelt länkad lista som en cirkulär länkad lista

Du uppmuntras att läsa och implementera C-koden nedan. Den illustrerar pekararitmetiken associerad med en cirkulär, enkellänkad lista.

#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:

1. De två första kodraderna är de nödvändiga inkluderade rubrikfilerna.
2. Nästa avsnitt definierar strukturen för varje självrefererande nod. Den innehåller ett värde och en pekare av samma typ som strukturen.
3. Varje strukturinstans länkar till andra strukturobjekt av samma typ.
4. Det finns olika funktionsprototyper för:
   1. Lägga till ett element i en tom länkad lista
   2. Insättning vid för närvarande pekade positionen för en cirkulär länkad lista.
   3. Infoga efter en viss indexeras värde i den länkade listan.
   4. Ta bort/ta bort efter en viss indexeras värde i den länkade listan.
   5. Ta bort på den för närvarande pekade positionen av en cirkulär länkad lista
5. 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:

1. För addToEmpty-koden, allokera en tom nod med hjälp av funktionen malloc().
2. Placera inkommande data i den tillfälliga noden.
3. Tilldela den tillfälliga noden till den sista och sätt dess nästa pekare till sig själv så att den enskilda noden pekar tillbaka till sig själv.
4. Returnera den sista pekaren tillbaka till main() / application-kontexten.

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

1. Om listan är tom, överlämna till addToEmpty() och returnera kontroll.
2. Skapa en tillfällig nod som placeras efter den aktuella noden.
3. Länka pekarna som visas i diagrammet ovan.
4. Returnera den sista pekaren, som matchar mönstret som användes 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:

1. Om listan är tom, ignorera söknyckeln, lägg till det aktuella objektet som enda nod i listan och returnera kontroll.
2. I varje iteration av do-while-slingan innehåller en tidigare pekare det senast genomsökta resultatet.
3. Först då sker nästa genomfartssteg.
4. Do-while-funktionen avslutas när måldata hittas eller när temperaturen når den sista pekaren igen. Följande kodblock avgör vad som ska göras med det hittade 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:

1. Om hela listan har gåtts igenom men objektet inte hittas, visas meddelandet "Elementet hittades inte" och kontrollen återlämnas till anroparen.
2. Om målnoden hittas, allokera en ny nod för värdet som ska infogas.
3. Länk den föregående noden till den nya noden och länka den nya nodens nästa pekare till temp (traversalvariabeln).
4. Detta placerar det nya elementet omedelbart efter målnoden i den cirkulära länkade listan. Kontrollen återgår sedan till anroparen.

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

1. För att ta bort den sista (nuvarande) noden, kontrollera först om listan är tom. Om den är det kan inget element tas bort.
2. Temp-variabeln flyttar en länk framåt.
3. Länka den sista pekaren till noden efter den första noden.
4. Frigör den tillfälliga pekaren för att avallokera den olänkade noden.

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

1. Precis som med den föregående borttagningsfunktionen, kontrollera först om listan är tom. Om den är det kan inget element tas bort.
2. Två pekare tilldelas specifika positioner för att lokalisera elementet som ska raderas.
3. Pekarna flyttas fram efter varandra (föregående spårs temperatur).
4. Traverseringen fortsätter tills målelementet hittas eller nästa pekare når den sista noden igen.

    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

1. Om hela den länkade listan genomsöks utan att målet hittas visas meddelandet "Element hittades inte".
2. Annars avlänkas elementet och frigörs i steg 3 och 4.
3. Den föregående pekaren är länkad till noden som temps nästa pekare pekar på (noden efter den som tas bort).
4. Temp-pekaren frigörs sedan.

...
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

1. Peek-traverseringen är inte möjlig om det finns noll noder — användaren måste först allokera eller infoga en nod.
2. Om det bara finns en nod krävs ingen genomgång – nodens innehåll skrivs ut direkt och while-slingan körs inte.
3. Om det finns mer än en nod skrivs varje objekt tillfälligt ut upp till det sista elementet.
4. I det ögonblick som det sista elementet nås avslutas loopen och funktionen återgår till main().

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-ring-schemaläggning i datornätverk.
• Används i displayenheter som digitala butikstavlor som kräver kontinuerlig dataöverföring.

Vanliga frågor