Kružni povezani popis: prednosti i nedostaci

Što je kružni povezani popis?

Kružna povezana lista je niz čvorova raspoređenih na takav način da se svaki čvor može vratiti do samog sebe. Ovdje je "čvor" samoreferencijalni element s pokazivačima na jedan ili dva čvora u njegovoj neposrednoj blizini.

Ispod je prikaz kružne povezane liste s 3 čvora.

Kružni povezani popis

Ovdje možete vidjeti da se svaki čvor može pratiti do samog sebe. Gore prikazani primjer je kružna jednostruko povezana lista.

Napomena: Najjednostavnija kružna povezana lista je čvor koji prati samo sebe kao što je prikazano

Kružni povezani popis

osnovni Operacije u kružno povezanim popisima

Osnovne operacije na kružnom povezanom popisu su:

  1. Umetanje
  2. Brisanje i
  3. obuhvaćanje
  • Umetanje je postupak postavljanja čvora na određeno mjesto u kružnom povezanom popisu.
  • Brisanje je postupak uklanjanja postojećeg čvora s povezanog popisa. Čvor se može identificirati po pojavljivanju njegove vrijednosti ili po položaju.
  • Prolazak kružnog povezanog popisa je proces prikazivanja cijelog sadržaja povezanog popisa i vraćanja natrag do izvornog čvora.

U sljedećem odjeljku razumjet ćete umetanje čvora i moguće vrste umetanja u kružnu pojedinačno povezanu listu.

Umetanje OperaANJE

U početku morate stvoriti jedan čvor koji pokazuje na sebe kao što je prikazano na ovoj slici. Bez ovog čvora, umetanje stvara prvi čvor.

Umetanje OperaANJE

Dalje, postoje dvije mogućnosti:

  • Umetanje na trenutnu poziciju kružnog povezanog popisa. To odgovara umetanju na početak kraja običnog pojedinačnog povezanog popisa. U kružnom povezanom popisu, početak i kraj su isti.
  • Umetanje nakon indeksiranog čvora. Čvor treba identificirati brojem indeksa koji odgovara vrijednosti njegovog elementa.

Za umetanje na početku/kraju kružnog povezanog popisa, to jest na mjestu gdje je dodan prvi čvor,

  • Morat ćete prekinuti postojeću samo-vezu s postojećim čvorom
  • Sljedeći pokazivač novog čvora povezat će se s postojećim čvorom.
  • Sljedeći pokazivač posljednjeg čvora pokazat će na umetnuti čvor.

NAPOMENA: Pokazivač koji je glavni token ili početak/kraj kruga može se promijeniti. I dalje će se vraćati na isti čvor tijekom obilaska, o čemu smo raspravljali naprijed.

Koraci pod (a) i-iii prikazani su u nastavku:

Umetanje OperaANJE

(Postojeći čvor)

Umetanje OperaANJE

KORAK 1) Prekini postojeću vezu

Umetanje OperaANJE

KORAK 2) Stvorite vezu prema naprijed (od novog čvora do postojećeg čvora)

Umetanje OperaANJE

KORAK 3) Napravite vezu petlje do prvog čvora

Zatim ćete pokušati umetanje nakon čvora.

Na primjer, umetnimo "VALUE2" nakon čvora s "VALUE0". Pretpostavimo da je početna točka čvor s "VALUE0".

  • Morat ćete prekinuti liniju između prvog i drugog čvora i postaviti čvor s "VALUE2" između.
  • Sljedeći pokazivač prvog čvora mora se povezati s ovim čvorom, a sljedeći pokazivač ovog čvora mora povezati s prethodnim drugim čvorom.
  • Ostatak aranžmana ostaje nepromijenjen. Svi čvorovi se mogu pratiti do sebe.

NAPOMENA: Budući da postoji ciklički raspored, umetanje čvora uključuje isti postupak za bilo koji čvor. Pokazivač koji dovršava ciklus dovršava ciklus kao i svaki drugi čvor.

Ovo je prikazano u nastavku:

Umetanje OperaANJE

(Recimo da postoje samo dva čvora. Ovo je trivijalan slučaj)

Umetanje OperaANJE

KORAK 1) Uklonite unutarnju vezu između povezanih čvorova

Umetanje OperaANJE

KORAK 2) Spojite čvor s lijeve strane na novi čvor

Umetanje OperaANJE

KORAK 3) Spojite novi čvor na čvor s desne strane.

brisanje OperaANJE

Pretpostavimo kružnu povezanu listu od 3 čvora. Slučajevi za brisanje navedeni su u nastavku:

  • Brisanje trenutnog elementa
  • Brisanje nakon elementa.

Brisanje na početku/kraju:

  1. Pređite do prvog čvora od posljednjeg čvora.
  2. Za brisanje od kraja, trebao bi postojati samo jedan korak prijelaza, od zadnjeg čvora do prvog čvora.
  3. Izbrišite vezu između posljednjeg čvora i sljedećeg čvora.
  4. Povežite posljednji čvor sa sljedećim elementom prvog čvora.
  5. Oslobodite prvi čvor.

brisanje OperaANJE

(Postojeće postavke)

brisanje OperaANJE

KORAK 1) Uklonite kružnu kariku

brisanje OperaANJE

KORACI 2) Uklonite vezu između prvog i sljedećeg, povežite posljednji čvor s čvorom koji slijedi nakon prvog

brisanje OperaANJE

KORAK 3) Oslobodite/oslobodite prvi čvor

Brisanje nakon čvora:

  1. Krećite se dok sljedeći čvor ne bude čvor koji se briše.
  2. Prijeđi do sljedećeg čvora, postavljajući pokazivač na prethodni čvor.
  3. Povežite prethodni čvor sa čvorom nakon sadašnjeg čvora, koristeći njegov sljedeći pokazivač.
  4. Oslobodite trenutni (odvezani) čvor.

brisanje OperaANJE

KORAK 1) Recimo da trebamo izbrisati čvor s "VALUE1."

brisanje OperaANJE

KORAK 2) Uklonite vezu između prethodnog čvora i trenutnog čvora. Povežite njegov prethodni čvor sa sljedećim čvorom na koji ukazuje trenutni čvor (sa VALUE1).

brisanje OperaANJE

KORAK 3) Oslobodite ili poništite trenutni čvor.

Prolazak kružnog povezanog popisa

Da biste prešli kružnu povezanu listu, počevši od posljednjeg pokazivača, provjerite je li sam zadnji pokazivač NULL. Ako je ovaj uvjet netočan, provjerite postoji li samo jedan element. U suprotnom, prijeđite pomoću privremenog pokazivača dok ponovno ne dosegnete zadnji pokazivač ili onoliko puta koliko je potrebno, kao što je prikazano na GIF-u u nastavku.

Prolazak kružnog povezanog popisa

Prednosti kružnog povezanog popisa

Neke od prednosti kružnih povezanih popisa su:

  1. Nema zahtjeva za NULL dodjelu u kodu. Kružni popis nikada ne pokazuje na NULL pokazivač osim ako nije potpuno oslobođen.
  2. Kružne povezane liste su korisne za krajnje operacije jer se početak i kraj podudaraju. Algorithms kao što je Round Robin raspoređivanje može uredno eliminirati procese koji su u redu čekanja na kružni način bez susretanja s visećim ili NULL-referencijalnim pokazivačima.
  3. Kružni povezani popis također obavlja sve uobičajene funkcije jednostruko povezanog popisa. Zapravo, kružno dvostruko povezane liste koji se raspravlja u nastavku može čak eliminirati potrebu za obilaskom u punoj dužini da bi se locirao element. Taj bi element u najboljem slučaju bio točno nasuprot početku, dovršavajući samo polovicu povezanog popisa.

Nedostaci kružnog povezanog popisa

Nedostaci korištenja kružnog povezanog popisa su sljedeći:

  1. Kružne liste su složene u usporedbi s pojedinačno povezane liste.
  2. RevDrugi kružni popis je složen u usporedbi s pojedinačnim ili dvostrukim popisima.
  3. Ako se njime ne rukuje pažljivo, kôd može ići u beskonačnu petlju.
  4. Teže pronaći kraj popisa i kontrolu petlje.
  5. Umetanjem na početku, moramo proći cijeli popis kako bismo pronašli posljednji čvor. (Perspektiva implementacije)

Jednostruko povezani popis kao kružni povezani popis

Potičemo vas da pokušate pročitati i implementirati kod u nastavku. Predstavlja aritmetiku pokazivača povezanu s kružnim povezanim popisima.

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

Pojedinačno povezani popis

Objašnjenje koda:

  1. Prva dva retka koda su potrebne uključene datoteke zaglavlja.
  2. Sljedeći odjeljak opisuje strukturu svakog samoreferentnog čvora. Sadrži vrijednost i pokazivač istog tipa kao i struktura.
  3. Svaka se struktura više puta povezuje s objektima strukture iste vrste.
  4. Postoje različiti prototipovi funkcija za:
    1. Dodavanje elementa na prazan povezani popis
    2. Umetanje u trenutno upereno položaj kružne povezane liste.
    3. Umetanje iza određenog indeksirano vrijednost na povezanom popisu.
    4. Uklanjanje/brisanje nakon određenog indeksirano vrijednost na povezanom popisu.
    5. Uklanjanje na trenutno naznačenoj poziciji kružnog povezanog popisa
  5. Posljednja funkcija ispisuje svaki element kroz kružni obilazak u bilo kojem stanju povezane 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)

Pojedinačno povezani popis

Objašnjenje koda:

  1. Za kod addEmpty, dodijelite prazan čvor pomoću funkcije malloc.
  2. Za ovaj čvor, smjestite podatke u varijablu temp.
  3. Dodijelite i povežite jedinu varijablu s privremenom varijablom
  4. Vratite posljednji element u main() / kontekst aplikacije.
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;
…

Pojedinačno povezani popis

Objašnjenje koda

  1. Ako nema elementa za umetanje, trebali biste dodati na prazan popis i vratiti kontrolu.
  2. Stvorite privremeni element koji ćete postaviti nakon trenutnog elementa.
  3. Povežite pokazivače kao što je prikazano.
  4. Vrati posljednji pokazivač kao u prethodnoj funkciji.
...
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");
...

Pojedinačno povezani popis

Objašnjenje koda:

  1. Ako nema elementa na popisu, zanemarite podatke, dodajte trenutnu stavku kao posljednju stavku na popisu i vratite kontrolu
  2. Za svaku iteraciju u do-while petlji osigurajte postojanje prethodnog pokazivača koji sadrži zadnji prijeđeni rezultat.
  3. Tek tada se može dogoditi sljedeće prelaženje.
  4. Ako su podaci pronađeni ili temp dosegne zadnji pokazivač, do-while se prekida. Sljedeći dio koda odlučuje što treba učiniti sa stavkom.
...
    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)
...

Pojedinačno povezani popis

Objašnjenje koda:

  1. Ako je cijeli popis pregledan, ali stavka nije pronađena, prikažite poruku "stavka nije pronađena" i zatim vratite kontrolu pozivatelju.
  2. Ako je pronađen čvor i/ili čvor još nije zadnji čvor, stvorite novi čvor.
  3. Veza prethodni čvor s novim čvorom. Povežite trenutni čvor s tempom (prolazna varijabla).
  4. Ovo osigurava da je element postavljen nakon određenog čvora na kružnom povezanom popisu. Povratak pozivatelju.
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)

Pojedinačno povezani popis

Objašnjenje koda

  1. Za uklanjanje samo zadnjeg (trenutačnog) čvora, provjerite je li ovaj popis prazan. Ako jest, tada se nijedan element ne može ukloniti.
  2. Varijabla temp samo prelazi jednu vezu naprijed.
  3. Povežite posljednji pokazivač s pokazivačem nakon prvog.
  4. Oslobodite pokazivač temp. Poništava zadnji nepovezani pokazivač.
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");
...

Pojedinačno povezani popis

Objašnjenje koda

  1. Kao i kod prethodne funkcije uklanjanja, provjerite nema li elementa. Ako je to istina, tada se nijedan element ne može ukloniti.
  2. upućuje dodjeljuju se određeni položaji za lociranje elementa koji se briše.
  3. Pokazivači su napredni, jedan iza drugog. (pret. iza temp.)
  4. Proces se nastavlja sve dok se element ne pronađe ili se sljedeći element ne vrati na zadnji pokazivač.
    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;	

Pojedinačno povezani popis

Objašnjenje programa

  1. Ako je element pronađen nakon obilaska cijelog povezanog popisa, prikazuje se poruka o pogrešci koja kaže da stavka nije pronađena.
  2. U suprotnom, element se odvaja i oslobađa u koracima 3 i 4.
  3. Prethodni pokazivač povezan je s adresom koju element koji treba izbrisati (temp) pokazuje kao "sljedeću".
  4. Temp pointer je stoga delociran i oslobođen.
...
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;
    }
}

Pojedinačno povezani popis

Objašnjenje koda

  1. Zavirivanje ili obilaženje nije moguće ako su potrebne nule. Korisnik treba dodijeliti ili umetnuti čvor.
  2. Ako postoji samo jedan čvor, nema potrebe za kretanjem, sadržaj čvora se može ispisati, a petlja while se ne izvršava.
  3. Ako postoji više od jednog čvora, tada temp ispisuje sve stavke do posljednjeg elementa.
  4. U trenutku kada se dosegne posljednji element, petlja se prekida, a funkcija vraća poziv glavnoj funkciji.

Primjene Kružnog povezanog popisa

  • Implementacija kružnog raspoređivanja u sistemskim procesima i kružnog raspoređivanja u grafici velike brzine.
  • Raspored token ringova u računalnim mrežama.
  • Koristi se u jedinicama za prikaz poput trgovačkih ploča koje zahtijevaju kontinuirano kretanje podataka.