circular linked list data structure c with illustration
Kompletný prehľad kruhového prepojeného zoznamu.
Kruhový prepojený zoznam je variáciou prepojeného zoznamu. Je to prepojený zoznam, ktorého uzly sú spojené tak, že tvoria kruh.
V kruhovo prepojenom zozname nie je nasledujúci ukazovateľ posledného uzla nastavený na hodnotu null, ale obsahuje adresu prvého uzla, čím sa vytvára kruh.
=> Navštívte tu a dozviete sa C ++ od nuly.
Čo sa dozviete:
Kruhový prepojený zoznam v C ++
Usporiadanie zobrazené nižšie slúži na jednotlivo prepojený zoznam.
Kruhový prepojený zoznam môže byť jednotlivo prepojený zoznam alebo dvojnásobne prepojený zoznam. V zozname s dvojnásobným kruhovým prepojením je predchádzajúci ukazovateľ prvého uzla spojený s posledným uzlom, zatiaľ čo ďalší ukazovateľ posledného uzla je spojený s prvým uzlom.
Jeho znázornenie je uvedené nižšie.
Vyhlásenie
Uzol v kruhovo prepojenom zozname môžeme vyhlásiť za akýkoľvek iný uzol, ako je uvedené nižšie:
struct Node { int data; struct Node *next; };
Aby sme mohli implementovať kruhový prepojený zoznam, udržiavame externý ukazovateľ „posledný“, ktorý ukazuje na posledný uzol v kruhovom prepojenom zozname. Preto posledný -> nasledujúci bude ukazovať na prvý uzol v prepojenom zozname.
Týmto zaistíme, že keď vložíme nový uzol na začiatok alebo na koniec zoznamu, nemusíme prechádzať celým zoznamom. Je to preto, že posledný ukazuje na posledný uzol, zatiaľ čo posledný -> ďalší ukazuje na prvý uzol.
To by nebolo možné, keby sme nasmerovali externý ukazovateľ na prvý uzol.
Základné operácie
Kruhový prepojený zoznam podporuje vloženie, odstránenie a prechod zoznamu. Teraz si podrobne povieme o každej z operácií.
Vloženie
Uzol môžeme vložiť do kruhového prepojeného zoznamu buď ako prvý uzol (prázdny zoznam), na začiatok, na koniec, alebo medzi ostatné uzly. Pozrime sa na každú z týchto operácií vkladania pomocou obrázkového znázornenia nižšie.
# 1) Vložte do prázdneho zoznamu
Ak v kruhovom zozname nie sú žiadne uzly a zoznam je prázdny, posledný ukazovateľ má hodnotu Null, potom vložíme nový uzol N nasmerovaním posledného ukazovateľa na uzol N, ako je uvedené vyššie. Nasledujúci ukazovateľ N bude smerovať na samotný uzol N, pretože existuje iba jeden uzol. Takto sa N stáva prvým aj posledným uzlom v zozname.
# 2) Vložte na začiatok zoznamu
Ako je znázornené na vyššie uvedenom obrázku, keď pridáme uzol na začiatku zoznamu, ďalší ukazovateľ posledného uzla ukazuje na nový uzol N, čím sa z neho stane prvý uzol.
N-> ďalší = posledný-> ďalší
Posledný -> ďalší = N
# 3) Vložte na koniec zoznamu
Ak chcete vložiť nový uzol na koniec zoznamu, vykonáme tieto kroky:
implementácia hash tabuľky v c ++
N-> ďalší = posledný -> ďalší;
posledný -> ďalší = N
posledný = N
# 4) Vložte medzi zoznam
Predpokladajme, že musíme vložiť nový uzol N medzi N3 a N4, najskôr musíme prejsť zoznamom a vyhľadať uzol, za ktorý sa má vložiť nový uzol, v tomto prípade jeho N3.
Po nájdení uzla vykonáme nasledujúce kroky.
N -> ďalší = N3 -> ďalší;
N3 -> ďalší = N
Toto vloží nový uzol N za N3.
Vymazanie
Operácia vymazania kruhového prepojeného zoznamu zahŕňa lokalizáciu uzla, ktorý sa má vymazať, a následné uvoľnenie jeho pamäte.
Za týmto účelom udržiavame dva ďalšie ukazovatele prúd a prev a potom prechádzame zoznamom, aby sme našli uzol. Daný uzol, ktorý sa má vymazať, môže byť prvý uzol, posledný uzol alebo uzol medzi nimi. V závislosti na umiestnení nastavíme ukazovatele prúd a prev a potom vymažeme uzol prúd.
Nižšie je zobrazené obrazové znázornenie operácie odstránenia.
Traverz
Traversal je technika návštevy každého uzla. V lineárne prepojených zoznamoch, ako je jednotlivo prepojený zoznam a dvojnásobne prepojené zoznamy, je prechod jednoduchý, keď navštívime každý uzol a zastavíme sa, keď narazíme na NULL.
To však nie je možné v zozname cyklicky prepojených odkazov. V kruhovo prepojenom zozname začíname od nasledujúceho posledného uzla, ktorý je prvým uzlom, a prechádzame každým uzlom. Zastavíme, keď sa opäť dostaneme k prvému uzlu.
Teraz predstavujeme implementáciu operácií kruhového prepojeného zoznamu pomocou C ++ a Java. Tu sme implementovali operácie vkladania, mazania a prechodu. Pre lepšie pochopenie sme kruhový prepojený zoznam zobrazili ako
K poslednému uzlu 50 teda opäť pripojíme uzol 10, ktorý je prvým uzlom, čím ho označíme ako kruhový prepojený zoznam.
#include using namespace std; struct Node { int data; struct Node *next; }; //insert a new node in an empty list struct Node *insertInEmpty(struct Node *last, int new_data) { // if last is not null then list is not empty, so return if (last != NULL) return last; // allocate memory for node struct Node *temp = new Node; // Assign the data. temp -> data = new_data; last = temp; // Create the link. last->next = last; return last; } //insert new node at the beginning of the list struct Node *insertAtBegin(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //set new data to node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; return last; } //insert new node at the end of the list struct Node *insertAtEnd(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //assign data to new node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; last = temp; return last; } //insert a new node in between the nodes struct Node *insertAfter(struct Node *last, int new_data, int after_item) { //return null if list is empty if (last == NULL) return NULL; struct Node *temp, *p; p = last -> next; do { if (p ->data == after_item) { temp = new Node; temp -> data = new_data; temp -> next = p -> next; p -> next = temp; if (p == last) last = temp; return last; } p = p -> next; } while(p != last -> next); cout << 'The node with data '< next; // Point to the first Node in the list. // Traverse the list starting from first node until first node is visited again do { cout < data <'; p = p -> next; } while(p != last->next); if(p == last->next) coutdata==key && (*head)->next==*head) { free(*head); *head=NULL; } Node *last=*head,*d; // If key is the head if((*head)->data==key) { while(last->next!=*head) // Find the last node of the list last=last->next; // point last node to next of head or second node of the list last->next=(*head)->next; free(*head); *head=last->next; } // end of list is reached or node to be deleted not there in the list while(last->next!=*head&&last->next->data!=key) { last=last->next; } // node to be deleted is found, so free the memory and display the list if(last->next->data==key) { d=last->next; last->next=d->next; cout<<'The node with data '< Výkon:
Vytvorený kruhový prepojený zoznam je nasledovný:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
Uzol s údajmi 10 sa vymaže zo zoznamu
Kruhový prepojený zoznam po odstránení 10 je nasledovný:
20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 20
Ďalej uvádzame implementáciu Java pre operácie kruhového prepojeného zoznamu.
//Java class to demonstrate circular linked list operations class Main { static class Node { int data; Node next; }; //insert a new node in the empty list static Node insertInEmpty(Node last, int new_data) { // if list is not empty, return if (last != null) return last; Node temp = new Node(); // create a new node temp.data = new_data; // assign data to new node last = temp; last.next = last; // Create the link return last; } //insert a new node at the beginning of the list static Node insertAtBegin(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); //set data for the node temp.data = new_data; temp.next = last.next; last.next = temp; return last; } //insert a new node at the end of the list static Node insertAtEnd(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); temp.data = new_data; temp.next = last.next; last.next = temp; last = temp; return last; } //insert node in between the nodes in the list static Node addAfter(Node last, int new_data, int after_item) { //if list is null, return if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == after_item) { temp = new Node(); temp.data = new_data; temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; { while(p != last.next); System.out.println('The node with data ' + after_item + ' not present in the list.'); return last; } //traverse the circular linked list static void traverse(Node last) { Node p; // If list is empty, return. if (last == null) { System.out.println('Cicular linked List is empty.'); return; } p = last.next; // Point to first Node of the list. // Traversing the list. do{ System.out.print(p.data + '==>'); p = p.next; } while(p != last.next); if(p == last.next) System.out.print(p.data); System.out.print('
'); } //delete a node from the list static Node deleteNode(Node head, int key) { //if list is null, return if (head == null) return null; // Find the required node that is to be deleted Node curr = head, prev = new Node(); while (curr.data != key) { if (curr.next == head) { System.out.printf('
Given node ' + key + ' is not found' + “in the list!'); break; } prev = curr; curr = curr.next; } // Check if node is only node if (curr.next == head) { head = null; return head; } // If more than one node, check if it is first node if (curr == head) { prev = head; while (prev.next != head) prev = prev.next; head = curr.next; prev.next = head; } // check if node is last node else if (curr.next == head) { prev.next = head; } else { prev.next = curr.next; } System.out.println('After deleting ' + key + ' the circular list is:'); traverse(head); return head; } // Main code public static void main(String() args){ Node last = null; last = insertInEmpty(last, 30); last = insertAtBegin(last, 20); last = insertAtBegin(last, 10); last = insertAtEnd(last, 40); last = insertAtEnd(last, 60); last = addAfter(last, 50, 40); System.out.println('Circular linked list created is:'); traverse(last); last = deleteNode(last,40); } }
Výkon:
Vytvorený kruhový prepojený zoznam je:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
Po odstránení 40 je kruhový zoznam:
10 ==> 20 ==> 30 ==> 50 ==> 60 ==> 10
Výhody nevýhody
Poďme diskutovať o niektorých výhodách a nevýhodách kruhového prepojeného zoznamu.
Výhody:
- Môžeme ísť do ktoréhokoľvek uzla a prechádzať z ktoréhokoľvek uzla. Len musíme prestať, keď znova navštívime ten istý uzol.
- Keď posledný uzol ukazuje na prvý uzol, prechod na prvý uzol z posledného uzla trvá iba jeden krok.
Nevýhody:
- Obrátenie kruhového prepojeného zoznamu je ťažkopádne.
- Pretože sú uzly spojené do tvaru kruhu, zoznam nemá správne začiatočné ani koncové označenie. Preto je ťažké nájsť koniec ovládacieho prvku zoznamu alebo slučky. Ak sa nebudete starať, implementácia by sa mohla skončiť v nekonečnej slučke.
- Nemôžeme sa vrátiť do predchádzajúceho uzla v jednom kroku. Celý zoznam musíme prechádzať od začiatku.
Aplikácie kruhového prepojeného zoznamu
- Aplikáciou kruhového prepojeného zoznamu v reálnom čase môže byť operačný systém s viacerými programami, v ktorom sa plánuje viac programov. Každý program dostane vyhradenú časovú značku na vykonanie, po ktorej sa prostriedky odovzdajú inému programu. Toto pokračuje nepretržite v cykle. Toto znázornenie je možné efektívne dosiahnuť pomocou kruhového prepojeného zoznamu.
- Hry, ktoré sa hrajú s viacerými hráčmi, je tiež možné znázorniť pomocou kruhového prepojeného zoznamu, v ktorom je každý hráč uzlom, ktorý má šancu hrať.
- Na predstavenie kruhového frontu môžeme použiť kruhový prepojený zoznam. Týmto spôsobom môžeme odstrániť dva ukazovatele vpredu a vzadu, ktoré sa používajú vo fronte. Namiesto toho môžeme použiť iba jeden ukazovateľ.
Záver
Kruhový prepojený zoznam je skupina uzlov, v ktorých sú uzly navzájom spojené a vytvárajú kruh. To znamená, že namiesto nastavenia nasledujúceho ukazovateľa posledného uzla na nulu je prepojený s prvým uzlom.
Kruhový prepojený zoznam je užitočný pri predstavovaní štruktúr alebo aktivít, ktoré je potrebné opakovať znova a znova po určitom časovom intervale, ako sú programy v prostredí s viacerými programami. Je to tiež výhodné pre návrh kruhového frontu.
Kruhové prepojené zoznamy podporujú rôzne operácie, ako je vkladanie, mazanie a prechádzanie. Preto sme operácie videli v tomto výučbe podrobne.
V našej ďalšej téme o dátových štruktúrach sa dozvieme o dátovej štruktúre zásobníka.
=> Ak chcete vidieť A-Z výučbových kurzov C ++, kliknite sem.
Odporúčané čítanie
- Prepojená dátová štruktúra zoznamu v C ++ s ilustráciou
- Štruktúra dát dvojnásobne prepojeného zoznamu v C ++ s ilustráciou
- Dátová štruktúra frontu v C ++ s ilustráciou
- Skladať dátovú štruktúru v C ++ s ilustráciou
- Štruktúra dát prioritného frontu v C ++ s ilustráciou
- Top 15 najlepších bezplatných nástrojov na dolovanie dát: najkomplexnejší zoznam
- Úvod do dátových štruktúr v C ++
- 15 najlepších nástrojov ETL v roku 2021 (kompletný aktualizovaný zoznam)