Listă circulară legată: Avantaje și dezavantaje

Ce este o listă circulară legată?

O listă circulară legată este o secvență de noduri aranjate astfel încât fiecare nod să poată fi retras la sine. Aici un „nod” este un element autoreferențial cu pointeri către unul sau două noduri din imediata apropiere.

Mai jos este o reprezentare a unei liste circulare legate cu 3 noduri.

Aici, puteți vedea că fiecare nod este retras la el însuși. Exemplul prezentat mai sus este o listă circulară cu legături unice.

Notă: Cea mai simplă listă circulară legată este un nod care urmărește numai la sine, așa cum se arată

pachet de bază Operaîn liste circulare legate

Operațiunile de bază pe o listă circulară legată sunt:

1. inserare
2. Ștergere și
3. traversal

• Inserarea este procesul de plasare a unui nod într-o poziție specificată în lista circulară legată.
• Ștergerea este procesul de eliminare a unui nod existent din lista legată. Nodul poate fi identificat prin apariția valorii sau prin poziția sa.
• Traversarea unei liste circulare legate este procesul de afișare a întregului conținut al listei legate și de revenire la nodul sursă.

În secțiunea următoare, veți înțelege inserarea unui nod și tipurile de inserare posibile într-o listă circulară legată individual.

inserare OperaTION

Inițial, trebuie să creați un nod care să se orienteze către sine, așa cum se arată în această imagine. Fără acest nod, inserarea creează primul nod.

În continuare, există două posibilități:

• Inserarea la poziția curentă a listei circulare legate. Aceasta corespunde inserării la începutul sfârșitului unei liste obișnuite de legături singulare. Într-o listă circulară legată, începutul și sfârșitul sunt același.
• Inserarea după un nod indexat. Nodul ar trebui să fie identificat printr-un număr de index corespunzător valorii elementului său.

Pentru inserarea la începutul/sfârșitul listei circulare legate, adică în poziția în care a fost adăugat primul nod,

• Va trebui să rupeți auto-linkul existent la nodul existent
• Următorul indicator al noului nod se va conecta la nodul existent.
• Următorul indicator al ultimului nod va indica nodul inserat.

NOTĂ: indicatorul care este token master sau începutul/sfârșitul cercului poate fi schimbat. Se va întoarce în continuare la același nod pe o traversare, discutată mai înainte.

Pașii de la (a) i-iii sunt prezentați mai jos:

(Nod existent)

PASUL 1) Rupe legătura existentă

PASUL 2) Creați o legătură directă (de la un nod nou la un nod existent)

PASUL 3) Creați o legătură în buclă către primul nod

În continuare, veți încerca inserarea după un nod.

De exemplu, să inserăm „VALOARE2” după nodul cu „VALOARE0”. Să presupunem că punctul de pornire este nodul cu „VALOARE0”.

• Va trebui să rupeți linia dintre primul și al doilea nod și să plasați nodul cu „VALUE2” între ele.
• Următorul pointer al primului nod trebuie să se conecteze la acest nod, iar următorul pointer al acestui nod trebuie să se conecteze la cel de-al doilea nod anterior.
• Restul aranjamentului rămâne neschimbat. Toate nodurile sunt trasabile către ele însele.

NOTĂ: Deoarece există un aranjament ciclic, inserarea unui nod implică aceeași procedură pentru orice nod. Indicatorul care finalizează un ciclu completează ciclul la fel ca orice alt nod.

Acesta este prezentat mai jos:

(Să spunem că există doar două noduri. Acesta este un caz trivial)

PASUL 1) Scoateți legătura interioară dintre nodurile conectate

PASUL 2) Conectați nodul din partea stângă la noul nod

PASUL 3) Conectați noul nod la nodul din partea dreaptă.

ștergere OperaTION

Să presupunem o listă circulară legată cu 3 noduri. Cazurile de ștergere sunt prezentate mai jos:

• Ștergerea elementului curent
• Ștergerea după un element.

Ștergere la început/sfârșit:

1. Traversați la primul nod de la ultimul nod.
2. Pentru a șterge de la sfârșit, ar trebui să existe un singur pas de traversare, de la ultimul nod la primul nod.
3. Ștergeți legătura dintre ultimul nod și următorul nod.
4. Conectați ultimul nod la următorul element al primului nod.
5. Eliberați primul nod.

(Configurație existentă)

PASUL 1) Scoateți legătura circulară

PASII 2) Eliminați legătura dintre primul și următorul, legați ultimul nod, la nodul care urmează pe primul

PASUL 3) Eliberați / dealocați primul nod

Ștergerea după un nod:

1. Traversați până când următorul nod este nodul care trebuie șters.
2. Traversați la următorul nod, plasând un indicator pe nodul anterior.
3. Conectați nodul anterior la nodul de după nodul prezent, folosind următorul indicator.
4. Eliberați nodul curent (deconectat).

PASUL 1) Să spunem că trebuie să ștergem un nod cu „VALUE1”.

PASUL 2) Eliminați legătura dintre nodul anterior și nodul curent. Conectați nodul său anterior cu următorul nod indicat de nodul curent (cu VALUE1).

PASUL 3) Eliberați sau dezalocați nodul curent.

Traversarea unei liste circulare legate

Pentru a parcurge o listă circulară legată, pornind de la un ultim pointer, verificați dacă ultimul pointer în sine este NULL. Dacă această condiție este falsă, verificați dacă există un singur element. În caz contrar, traversați folosind un indicator temporar până când ultimul indicator este atins din nou, sau de câte ori este necesar, așa cum se arată în GIF de mai jos.

Avantajele listei circulare legate

Unele dintre avantajele listelor circulare legate sunt:

1. Nicio cerință pentru o atribuire NULL în cod. Lista circulară nu indică niciodată către un pointer NULL decât dacă este complet dealocată.
2. Listele circulare legate sunt avantajoase pentru operațiunile de sfârșit, deoarece începutul și sfârșitul coincid. Algorithms cum ar fi programarea Round Robin poate elimina cu grijă procesele care sunt puse în coadă într-o manieră circulară, fără a întâmpina indicatori de referință suspendați sau NULL.
3. Lista circulară legată îndeplinește, de asemenea, toate funcțiile obișnuite ale unei liste conectate unic. De fapt, circular liste dublu legate discutat mai jos poate chiar elimina necesitatea unei traversări pe toată lungimea pentru a localiza un element. Acest element ar fi cel mult doar exact opus față de început, completând doar jumătate din lista legată.

Dezavantajele listei circulare legate

Dezavantajele utilizării unei liste circulare sunt mai jos:

1. Listele circulare sunt complexe în comparație cu liste legate individual.
2. RevEsa de liste circulare este un complex în comparație cu listele individuale sau duble.
3. Dacă nu este tratat cu atenție, atunci codul poate merge într-o buclă infinită.
4. Mai greu de găsit sfârșitul listei și controlul buclei.
5. Inserând la Start, trebuie să parcurgem lista completă pentru a găsi ultimul nod. (Perspectiva implementării)

Listă legată individual ca listă circulară legată

Sunteți încurajat să încercați să citiți și să implementați codul de mai jos. Prezintă aritmetica pointerului asociat listelor circulare legate.

#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()
{
...

Explicația codului:

1. Primele două linii de cod sunt fișierele de antet incluse necesare.
2. Următoarea secțiune descrie structura fiecărui nod autoreferențial. Conține o valoare și un pointer de același tip ca și structura.
3. Fiecare structură se leagă în mod repetat la obiecte de structură de același tip.
4. Există diferite prototipuri de funcții pentru:
   1. Adăugarea unui element la o listă conexă goală
   2. Inserarea la în prezent arătată poziţia unei liste circulare legate.
   3. Inserarea după un anume indexate valoare din lista legată.
   4. Eliminarea/Ștergerea după un anumit indexate valoare din lista legată.
   5. Eliminarea în poziția curentă a unei liste circulare legate
5. Ultima funcție imprimă fiecare element printr-o traversare circulară în orice stare a listei legate.

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)

Explicația codului:

1. Pentru codul addEmpty, alocă un nod gol folosind funcția malloc.
2. Pentru acest nod, plasați datele în variabila temp.
3. Atribuiți și legați singura variabilă la variabila temp
4. Returnează ultimul element în contextul main() / aplicație.

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;
…

Explicația codului

1. Dacă nu există niciun element de inserat, atunci ar trebui să vă asigurați că adăugați la o listă goală și returnați controlul.
2. Creați un element temporar pe care să îl plasați după elementul curent.
3. Conectați indicatorii așa cum se arată.
4. Întoarceți ultimul indicator ca în funcția anterioară.

...
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");
...

Explicația codului:

1. Dacă nu există niciun element în listă, ignorați datele, adăugați elementul curent ca ultimul element din listă și returnați controlul
2. Pentru fiecare iterație din bucla do-while asigurați-vă că există un indicator anterior care conține ultimul rezultat parcurs.
3. Numai atunci poate avea loc următoarea traversare.
4. Dacă datele sunt găsite, sau temp ajunge înapoi la ultimul pointer, do-while se termină. Următoarea secțiune a codului decide ce trebuie făcut cu elementul.

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

Explicația codului:

1. Dacă întreaga listă a fost parcursă, dar articolul nu a fost găsit, afișați un mesaj „articol negăsit” și apoi returnați controlul apelantului.
2. Dacă a fost găsit un nod și/sau nodul nu este încă ultimul nod, atunci creați un nou nod.
3. Link nodul anterior cu noul nod. Conectați nodul curent cu temp (variabila traversală).
4. Acest lucru asigură că elementul este plasat după un anumit nod din lista circulară legată. Reveniți la apelant.

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)

Explicația codului

1. Pentru a elimina doar ultimul nod (actual), verificați dacă această listă este goală. Dacă este, atunci niciun element nu poate fi îndepărtat.
2. Variabila temp parcurge doar o legătură înainte.
3. Conectați ultimul indicator cu indicatorul de după primul.
4. Eliberați indicatorul de temperatură. Dealocarea ultimului pointer nelegat.

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");
...

Explicația codului

1. Ca și în cazul funcției anterioare de îndepărtare, verificați dacă nu există niciun element. Dacă acest lucru este adevărat, atunci niciun element nu poate fi eliminat.
2. Pointeri li se atribuie poziții specifice pentru a localiza elementul de șters.
3. Indicatoarele sunt avansate, unul în spatele celuilalt. (anterior în spatele temperaturii)
4. Procesul continuă până când este găsit un element sau următorul element se întoarce la ultimul indicator.

    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;	

Explicația programului

1. Dacă elementul a fost găsit după parcurgerea întregii liste legate, este afișat un mesaj de eroare care spune că elementul nu a fost găsit.
2. În caz contrar, elementul este deconectat și eliberat în pașii 3 și 4.
3. Pointerul anterior este legat de adresa indicată ca „următorul” de elementul care trebuie șters (temp).
4. Prin urmare, indicatorul temp este dealocat și eliberat.

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

Explicația codului

1. Privirea sau traversarea nu este posibilă dacă este nevoie de zero. Utilizatorul trebuie să aloce sau să insereze un nod.
2. Dacă există un singur nod, nu este nevoie să traversați, conținutul nodului poate fi imprimat, iar bucla while nu se execută.
3. Dacă există mai mult de un nod, atunci temp printează tot elementul până la ultimul element.
4. În momentul în care ultimul element este atins, bucla se termină, iar funcția returnează apelul la funcția principală.

Aplicații ale listei circulare legate

• Implementarea programării round-robin în procesele de sistem și a programării circulare în grafica de mare viteză.
• Programarea token rings în rețelele de calculatoare.
• Este folosit în unități de afișare, cum ar fi panourile de magazin, care necesită parcurgerea continuă a datelor.