Cirkulær kædet liste: fordele og ulemper

Hvad er en cirkulær linket liste?

En cirkulær sammenkædet liste er en sekvens af noder arrangeret på en sådan måde, at hver node kan spores tilbage til sig selv. Her er en "node" et selvrefererende element med pointere til en eller to noder i dens umiddelbare nærhed.

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

Her kan du se, at hver node kan spores til sig selv. Eksemplet vist ovenfor er en cirkulær enkelt-linket liste.

Bemærk: Den mest simple cirkulære sammenkædede liste er en node, som kun sporer sig selv som vist

Grundlæggende Operationer i Circular Linked lister

De grundlæggende handlinger 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 linket liste er processen med at vise hele den linkede listes indhold og gå tilbage til kildenoden.

I det næste afsnit vil du forstå indsættelse af en node og de mulige typer af indsættelse i en cirkulær enkeltforbundet liste.

Indsættelse Operation

I første omgang skal du oprette en node, der peger på sig selv som vist på dette billede. Uden denne node opretter indsættelse den første node.

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 begyndelsen af ​​slutningen af ​​en almindelig singular sammenkædet liste. I en cirkulær sammenkædet liste er begyndelsen og slutningen den samme.
• Indsættelse efter en indekseret node. Noden skal identificeres med et indeksnummer svarende til dens elementværdi.

For at indsætte i begyndelsen/slutningen af ​​den cirkulære sammenkædede liste, det vil sige på den position, hvor den første node nogensinde blev tilføjet,

• 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: Den markør, der er token-masteren eller begyndelsen/slutningen af ​​cirklen, kan ændres. Det vil stadig vende tilbage til den samme knude på en gennemgang, diskuteret forud.

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.

Lad os f.eks. indsætte "VALUE2" efter knudepunktet med "VALUE0". Lad os antage, at udgangspunktet er noden med "VALUE0".

• Du bliver nødt til at bryde linjen mellem den første og anden node og placere noden med "VALUE2" imellem.
• Den første nodes næste pointer skal linke til denne node, og denne nodes næste pointer skal linke til den tidligere anden node.
• Resten af ​​arrangementet forbliver uændret. Alle noder kan spores til sig selv.

BEMÆRK: Da der er et cyklisk arrangement, involverer indsættelse af en node den samme procedure for enhver node. Markøren, der fuldfører en cyklus, fuldender cyklussen ligesom enhver anden node.

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

Lad os antage en 3-node cirkulær linket liste. Sagerne til sletning er angivet nedenfor:

• 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. For at slette fra slutningen skal der kun være ét gennemløbstrin, fra den sidste knude til den første knude.
3. Slet linket mellem den sidste node og den næste 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 led

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 / deallokér den første node

Sletning efter en node:

1. Kør 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 aktuelle node. Forbind dens forrige node med den næste node, som den aktuelle node peger på (med VALUE1).

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

Gennemgang af en cirkulær sammenkædet liste

For at krydse en cirkulær linket liste, startende fra en sidste pointer, skal du kontrollere, om selve den sidste pointer er NULL. Hvis denne betingelse er falsk, skal du kontrollere, om der kun er ét element. Ellers skal du gå gennem en midlertidig markør, indtil den sidste markør er nået igen, eller så mange gange som nødvendigt, som vist i GIF'en 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 slutoperationer, da begyndelsen og slutningen falder sammen. Algorithms Som f.eks. Round Robin-planlægningen, kan man pænt eliminere processer, der er i kø på en cirkulær måde uden at støde på dinglende eller NULL-henvisningspunkter.
3. Cirkulær linket liste udfører også alle almindelige funktioner af en enkelt linket liste. Faktisk cirkulær dobbeltforbundne lister diskuteret nedenfor kan endda eliminere behovet for en gennemgang i fuld længde for at lokalisere et element. Det element ville højst kun være det modsatte af starten og fuldende kun halvdelen af ​​den linkede liste.

Ulemper ved Circular Linked List

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

1. Cirkulære lister er komplekse i forhold til enkelt forbundne lister.
2. RevErse af cirkulær liste er et kompleks sammenlignet med enkelt- eller dobbeltlister.
3. Hvis den ikke håndteres forsigtigt, kan koden gå i en uendelig løkke.
4. Sværere at finde slutningen af ​​listen og loop kontrol.
5. Når vi indsætter ved Start, skal vi gennemse hele listen for at finde den sidste node. (Implementeringsperspektiv)

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

Du opfordres til at forsøge at læse og implementere koden nedenfor. Den præsenterer pointer-aritmetikken forbundet med cirkulære sammenkædede 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 af kode:

1. De første to linjer kode er de nødvendige medfølgende header-filer.
2. Det næste afsnit beskriver strukturen af ​​hver selvrefererende knude. Den indeholder en værdi og en pointer af samme type som strukturen.
3. Hver struktur linker gentagne gange til 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 addEmpty-koden skal du tildele en tom node ved hjælp af malloc-funktionen.
2. For denne node skal du placere dataene til temp-variablen.
3. Tildel og link den eneste variabel til temp-variablen
4. Returner det sidste element til main() / applikationskonteksten.

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 der ikke er noget element at indsætte, så skal du sørge for at tilføje til en tom liste og returnere kontrol.
2. Opret et midlertidigt element, der skal placeres efter det aktuelle element.
3. Link pointerne som vist.
4. Returner den sidste markør som 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 der ikke er noget element på listen, ignorer dataene, tilføj det aktuelle element som det sidste element på listen og returner kontrolelementet
2. For hver iteration i do-while-løkken skal du sikre dig, at der er en tidligere pointer, der holder det sidste gennemkørte resultat.
3. Først derefter kan den næste krydsning ske.
4. Hvis dataene er fundet, eller temperaturen når tilbage til den sidste pointer, afsluttes do-while. Det næste afsnit af koden bestemmer, hvad der skal gøres med emnet.

...
    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 er fundet, skal du vise en "element ikke fundet"-meddelelse og derefter returnere kontrollen til den, der ringer.
2. Hvis der er fundet en node, og/eller noden endnu ikke er den sidste node, så opret en ny node.
3. Link den forrige node med den nye node. Forbind den aktuelle node med temp (gennemløbsvariablen).
4. Dette sikrer, at elementet placeres efter en bestemt node i den cirkulære sammenkædede liste. Vend tilbage til den, der 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 af kode

1. For kun at fjerne den sidste (nuværende) node, skal du kontrollere, om denne liste er tom. Hvis det er det, kan intet element fjernes.
2. Temperaturvariablen krydser kun et led fremad.
3. Link den sidste markør til markøren efter den første.
4. Frigør temp pointer. Det deallokerer den ikke-linkede sidste pointer.

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 tidligere fjernelsesfunktion skal du kontrollere, om der ikke er noget element. Hvis dette er sandt, kan intet element fjernes.
2. Pointers er tildelt specifikke positioner for at finde det element, der skal slettes.
3. Viserne er fremført, den ene bag den anden. (forrige bag temp)
4. Processen fortsætter, indtil et element er fundet, eller det næste element går tilbage til den sidste markør.

    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 elementet fundet efter at have gennemgået hele den linkede liste, vises en fejlmeddelelse, der siger, at elementet ikke blev fundet.
2. Ellers bliver elementet delinket og frigivet i trin 3 og 4.
3. Den forrige pointer er knyttet til den adresse, der peges som "næste" af elementet, der skal slettes (temp).
4. Temp-markøren er derfor deallokeret og frigivet.

...
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. Kig eller gennemkig er ikke muligt, hvis der ikke er behov for nul. Brugeren skal allokere eller indsætte en node.
2. Hvis der kun er én node, er der ingen grund til at krydse, nodens indhold kan udskrives, og while-løkken udføres ikke.
3. Hvis der er mere end én node, så udskriver den midlertidige hele elementet indtil det sidste element.
4. I det øjeblik det sidste element er nået, afsluttes løkken, og funktionen returnerer kald til hovedfunktionen.

Anvendelser af den cirkulære linkede liste

• Implementering af round-robin planlægning i systemprocesser og cirkulær planlægning i højhastighedsgrafik.
• Token-ringe planlægning i computernetværk.
• Det bruges i displayenheder som butikstavler, der kræver kontinuerlig gennemgang af data.