Cirkulær kædet liste: fordele og ulemper

Hvad er en cirkulær linket liste?

En cirkulær linket liste er en sekvens af noder arrangeret således at hver node kan gentagestractil sig selv. Hver "node" er et selvrefererende element med peger på en eller to noder i sin umiddelbare nærhed.

Nedenfor er en afbildning af en cirkulær sammenkædet liste med 3 noder.

Her kan du se, at hver node er genindførttracmulig for sig selv. Eksemplet vist ovenfor er en cirkulær enkeltlænket liste.

Bemærk: Den enkleste cirkulære linkede liste er en enkelt node, hvis næste pointer traces tilbage til sig selv, som vist nedenfor.

Grundlæggende Operationer i cirkulære sammenkædede lister

De tre grundlæggende operationer på en cirkulær, sammenkædet liste er:

1. Indsættelse
2. Sletning og
3. Traversal

• Indsættelse er processen med at placere en node på en specificeret position i den cirkulære sammenkædede liste.
• Sletning er processen med at fjerne en eksisterende node fra den sammenkædede liste. Noden kan identificeres ved forekomsten af ​​dens værdi eller ved dens position.
• Gennemgang af en cirkulær, sammenkædet liste er processen med at vise hele den sammenkædede listes indhold og genlæse den.tractilbage til kildenoden.

Det næste afsnit forklarer, hvordan indsættelse fungerer, og de to typer indsættelse, der er mulige i en cirkulær, enkeltstående linket liste.

Indsættelse Operation

Du opretter først en node, hvis næste pointer peger tilbage til sig selv, som vist nedenfor. Uden denne seed-node bliver den første indsættelse den første node på listen.

Dernæst er der to muligheder:

• Indsættelse på den aktuelle position af den cirkulære, sammenkædede liste. Dette svarer til indsættelse i enten begyndelsen eller slutningen af ​​en almindelig, enkeltstående, sammenkædet liste – i en cirkulær, sammenkædet liste er begyndelsen og slutningen det samme punkt.
• Indsættelse efter en indekseret node. Noden skal identificeres med et indeksnummer svarende til dens elementværdi.

For at indsætte i begyndelsen eller slutningen af ​​den cirkulære sammenkædede liste – det vil sige på den position, hvor den allerførste node blev tilføjet – skal du følge nedenstående trin:

• Du bliver nødt til at bryde det eksisterende selvlink til den eksisterende node
• Den nye nodes næste pointer vil linke til den eksisterende node.
• Den sidste nodes næste pointer vil pege på den indsatte node.

BEMÆRK: Markøren, der markerer begyndelsen eller slutningen af ​​cirklen, kan tildeles en hvilken som helst node. En gennemgang vil stadig vende tilbage til den samme node, som beskrevet senere i denne artikel.

Trin i (a) i-iii er vist nedenfor:

(Eksisterende node)

Trin 1) Bryd det eksisterende link

Trin 2) Opret et fremadgående link (fra ny node til en eksisterende node)

Trin 3) Opret et løkkelink til den første knude

Dernæst vil du prøve at indsætte efter en node.

Indsæt for eksempel "VÆRDI2" efter noden, der indeholder "VÆRDI0", idet udgangspunktet er noden med "VÆRDI0".

• Bryd forbindelsen mellem den første og anden node, og placer noden med "VALUE2" imellem.
• Den første nodes næste pointer linker til den nye node, og den nye nodes næste pointer linker til det, der tidligere var den anden node.
• Resten af ​​arrangementet forbliver uændret. Alle noder er genindlæst.tractilgængelige for sig selv.

BEMÆRK: Da arrangementet er cyklisk, er proceduren for indsættelse af en node identisk, uanset hvilken position du vælger. Den markør, der lukker cyklussen, opfører sig som enhver anden markør på listen.

Dette er vist nedenfor:

(Lad os sige, at der kun er to noder. Dette er et trivielt tilfælde)

Trin 1) Fjern den indre forbindelse mellem de tilsluttede noder

Trin 2) Forbind den venstre knude til den nye knude

Trin 3) Forbind den nye node til noden på højre side.

sletning Operation

Antag en cirkulær, sammenkædet liste med 3 noder. De to sletningstilfælde er:

• Sletning af det aktuelle element
• Sletning efter et element.

Sletning i begyndelsen/slutningen:

1. Gå til den første knude fra den sidste knude.
2. Sletning fra slutningen kræver kun ét gennemløbstrin, fra den sidste node til den første node.
3. Slet linket mellem den sidste node og den første node.
4. Link den sidste node til det næste element i den første node.
5. Frigør den første node.

(Eksisterende opsætning)

Trin 1) Fjern det cirkulære link

Trin 2) Fjern linket mellem den første og den næste, link den sidste node, til noden efter den første

Trin 3) Frigør / afalloker den første node

Sletning efter en node:

1. Gå gennem indtil den næste node er den node, der skal slettes.
2. Gå til næste knudepunkt, og placer en markør på den forrige knude.
3. Forbind den forrige node til noden efter den nuværende node ved hjælp af dens næste markør.
4. Frigør den aktuelle (afkoblede) node.

Trin 1) Lad os sige, at vi skal slette en node med "VALUE1."

Trin 2) Fjern forbindelsen mellem den forrige node og den nuværende node, og forbind derefter den forrige node direkte med den node, som den nuværende nodes næste pointer peger på (noden efter VALUE1).

Trin 3) Frigør eller tildel den aktuelle node.

Gennemgang af en cirkulær sammenkædet liste

For at bevæge sig gennem en cirkulær, sammenkædet liste fra en sidste pointer, skal du først kontrollere, om den sidste pointer er NULL. Hvis den ikke er NULL, skal du kontrollere, om listen kun har ét element. Ellers skal du bevæge dig gennem listen med en midlertidig pointer, indtil du når den sidste pointer igen, som vist i animationen nedenfor.

Fordele ved Circular Linked List

Nogle af fordelene ved cirkulære sammenkædede lister er:

1. Intet krav om en NULL-opgave i koden. Den cirkulære liste peger aldrig på en NULL-markør, medmindre den er fuldt deallokeret.
2. Cirkulære, sammenkædede lister er fordelagtige til listeslutningsoperationer, fordi begyndelsen og slutningen falder sammen. Algorithms såsom round-robin-planlægning kan bevæge sig gennem processer i kø uden at støde på dinglende eller NULL-pointere.
3. En cirkulær linket liste understøtter stadig alle de almindelige operationer i en enkelt linket liste. En cirkulær dobbelt linket liste kan endda eliminere behovet for en fuld gennemgang for at finde et element — i værste fald sidder målet overfor startmarkøren, så højst halvdelen af ​​listen skal gås.

Ulemper ved Circular Linked List

Ulemperne ved at bruge en cirkulær linket liste er nedenfor:

1. Cirkulære lister er mere komplekse end enkelt forbundne lister.
2. RevDet er mere komplekst at slette en cirkulær liste end at vende en enkelt- eller dobbeltlænket liste.
3. Hvis loop-afslutning ikke håndteres omhyggeligt, kan traversal-koden indgå i en uendelig løkke.
4. Det er sværere at finde slutningen af ​​listen og at skrive korrekte loop-kontrolbetingelser.
5. Indsættelse i starten kræver, at man gennemløber hele listen for at nå den sidste node (fra et implementeringsperspektiv).

Enkelt lænket liste som en cirkulær lænket liste

Du opfordres til at læse og implementere C-koden nedenfor. Den illustrerer pointeraritmetikken forbundet med en cirkulær enkeltkædet liste.

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

1. De første to linjer kode er de nødvendige medfølgende header-filer.
2. Det næste afsnit definerer strukturen for hver selvrefererende node. Den indeholder en værdi og en pointer af samme type som strukturen.
3. Hver strukturinstans linker til andre strukturobjekter af samme type.
4. Der er forskellige funktionsprototyper til:
   1. Tilføjelse af et element til en tom sammenkædet liste
   2. Indsættelse ved i øjeblikket pegede placeringen af ​​en cirkulær sammenkædet liste.
   3. Indsættelse efter en bestemt indekseret værdi i den linkede liste.
   4. Fjernelse/sletning efter en bestemt indekseret værdi i den linkede liste.
   5. Fjernelse ved den aktuelt pegede position af en cirkulær sammenkædet liste
5. Den sidste funktion udskriver hvert element gennem en cirkulær gennemløb i en hvilken som helst tilstand af den sammenkædede liste.

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 af kode:

1. For addToEmpty-koden skal du allokere en tom node ved hjælp af malloc()-funktionen.
2. Placer de indgående data i den midlertidige node.
3. Tildel den midlertidige node til den sidste, og indstil dens næste pointer til sig selv, så den enkelte node peger tilbage på sig selv.
4. Returner den sidste pointer tilbage til main() / application-konteksten.

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 af kode

1. Hvis listen er tom, skal den overdrages til addToEmpty() og kontrol returneres.
2. Opret en midlertidig node, der skal placeres efter den aktuelle node.
3. Forbind pointerne som vist i diagrammet ovenfor.
4. Returner den sidste pointer, der matcher det mønster, der blev brugt i den forrige 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");
...

Forklaring af kode:

1. Hvis listen er tom, ignorer søgenøglen, tilføj det aktuelle element som den eneste node på listen og returner kontrol.
2. I hver iteration af do-while-løkken indeholder en tidligere pointer det sidst gennemløbne resultat.
3. Først derefter finder det næste gennemløbstrin sted.
4. Do-while-funktionen afsluttes, når måldataene findes, eller når temperaturen når den sidste pointer igen. Den følgende kodeblok bestemmer, hvad der skal ske med det fundne element.

...
    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 af kode:

1. Hvis hele listen er blevet gennemgået, men elementet ikke findes, vises meddelelsen "Element ikke fundet", og kontrollen gives tilbage til den, der kalder.
2. Hvis målnoden findes, skal du allokere en ny node til den værdi, der skal indsættes.
3. Link den forrige node til den nye node, og link den nye nodes næste pointer til temp (traversalvariablen).
4. Dette placerer det nye element umiddelbart efter målnoden i den cirkulære, sammenkædede liste. Kontrollen vender derefter tilbage til den, der kalder.

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 af kode

1. For at fjerne den sidste (nuværende) node skal du først kontrollere, om listen er tom. Hvis den er det, kan intet element fjernes.
2. Temp-variablen rykker et led fremad.
3. Forbind den sidste pointer med noden efter den første node.
4. Frigør den midlertidige pointer for at deallokere den ikke-tilknyttede node.

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 af kode

1. Som med den forrige fjernelsesfunktion skal du først kontrollere, om listen er tom. Hvis den er det, kan intet element fjernes.
2. to pointers er tildelt specifikke positioner for at finde det element, der skal slettes.
3. Viserne flyttes frem efter hinanden (tidligere spor temperatur).
4. Gennemgangen fortsætter, indtil målelementet findes, eller den næste pointer når den sidste node 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;

Forklaring af program

1. Hvis hele den sammenkædede liste gennemgås uden at finde målet, vises meddelelsen "Element ikke fundet".
2. Ellers afkobles elementet og frigøres i trin 3 og 4.
3. Den forrige pointer er linket til den node, som temps næste pointer peger på (noden efter den, der slettes).
4. Temp-viseren frigøres derefter.

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

1. Peek-traversal er ikke mulig, hvis der er nul noder — brugeren skal først allokere eller indsætte en node.
2. Hvis der kun er én node, kræves der ingen gennemgang — nodens indhold udskrives direkte, og while-løkken udføres ikke.
3. Hvis der er mere end én node, udskriver den midlertidigt alle elementer op til det sidste element.
4. I det øjeblik det sidste element nås, afsluttes løkken, og funktionen returnerer kontrol til main().

Anvendelser af den cirkulære linkede liste

• Implementering af round-robin planlægning i systemprocesser og cirkulær planlægning i højhastighedsgrafik.
• Token-ring-planlægning i computernetværk.
• Anvendes i displayenheder såsom digitale butikstavler, der kræver kontinuerlig datagennemstrømning.

Ofte Stillede Spørgsmål