circular linked list data structure c with illustration
En fullständig översikt över cirkulär länkad lista.
En cirkulär länkad lista är en variant av den länkade listan. Det är en länkad lista vars noder är anslutna på ett sådant sätt att den bildar en cirkel.
I den cirkulära länkade listan är nästa pekare för den sista noden inte inställd på null men den innehåller adressen till den första noden och bildar således en cirkel.
=> Besök här för att lära dig C ++ från Scratch.
Vad du kommer att lära dig:
Cirkulär länkad lista i C ++
Arrangemanget som visas nedan är för en enskilt länkad lista.
En cirkulär länkad lista kan vara en enstaka länkad lista eller en dubbel länkad lista. I en dubbelt cirkulär länkad lista är den föregående pekaren i den första noden ansluten till den sista noden medan nästa pekare i den sista noden är ansluten till den första noden.
Dess representation visas nedan.
Deklaration
Vi kan förklara en nod i en cirkulär länkad lista som vilken annan nod som helst som visas nedan:
struct Node { int data; struct Node *next; }; För att implementera den cirkulära länkade listan upprätthåller vi en extern pekare 'sista' som pekar på den sista noden i den cirkulärlänkade listan. Därför kommer sista-> nästa att peka på den första noden i den länkade listan.
Genom att göra detta ser vi till att när vi infogar en ny nod i början eller i slutet av listan behöver vi inte korsa hela listan. Detta beror på att de sista pekar på den sista noden medan sista-> nästa pekar på den första noden.
Detta hade inte varit möjligt om vi hade pekat den externa pekaren mot den första noden.
Grundläggande funktioner
Den cirkulära länkade listan stöder infogning, radering och genomgång av listan. Vi kommer att diskutera var och en av operationerna i detalj nu.
Införande
Vi kan infoga en nod i en cirkulär länkad lista antingen som en första nod (tom lista), i början, i slutet eller mellan de andra noderna. Låt oss se var och en av dessa insättningsoperationer med hjälp av en bildrepresentation nedan.
# 1) Infoga i en tom lista
När det inte finns några noder i den cirkulära listan och listan är tom, är den sista pekaren noll, sedan infogar vi en ny nod N genom att peka den sista pekaren mot noden N som visas ovan. Nästa pekare på N kommer att peka på själva noden N eftersom det bara finns en nod. Således blir N den första såväl som sista noden i listan.
# 2) Infoga i början av listan
Som visas i ovanstående representation, när vi lägger till en nod i början av listan, pekar nästa pekare för den sista noden på den nya noden N och gör den därmed till en första nod.
N-> nästa = sista-> nästa
Sista-> nästa = N
# 3) Infoga i slutet av listan
För att infoga en ny nod i slutet av listan följer vi dessa steg:
c ++ slumpmässigt tal mellan 0 och 10
N-> nästa = sista -> nästa;
sista -> nästa = N
sista = N
# 4) Infoga mellan listan
Anta att vi måste infoga en ny nod N mellan N3 och N4, vi måste först korsa listan och lokalisera noden efter vilken den nya noden ska infogas, i detta fall dess N3.
När noden är lokaliserad utför vi följande steg.
N -> nästa = N3 -> nästa;
N3 -> nästa = N
Detta infogar en ny nod N efter N3.
Radering
Raderingsfunktionen för den cirkulära länkade listan innebär att lokalisera noden som ska raderas och sedan frigöra dess minne.
För detta behåller vi ytterligare två pekare curr och prev och korsar sedan listan för att lokalisera noden. Den givna noden som ska raderas kan vara den första noden, den sista noden eller noden däremellan. Beroende på plats ställer vi in curr- och prev-pekare och tar sedan bort curr-noden.
En bildrepresentation av raderingsoperationen visas nedan.
Traversal
Traversal är en teknik för att besöka varje nod. I linjära länkade listor som enstaka länkade listor och dubbelt länkade listor är det lätt att korsa när vi besöker varje nod och stannar när NULL påträffas.
Detta är dock inte möjligt i en cirkulär länkad lista. I en cirkulär länkad lista börjar vi från nästa av den sista noden som är den första noden och korsar varje nod. Vi slutar när vi återigen når den första noden.
Nu presenterar vi en implementering av de cirkulära länkoperationerna med C ++ och Java. Vi har implementerat insättning, radering och traversal-operationer här. För en klar förståelse har vi avbildat den cirkulära länkade listan som
Således till den sista noden 50 fäster vi återigen noden 10, som är den första noden, vilket indikerar den som en cirkulär länkad lista.
#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 '< Produktion:
Den cirkulära länkade listan som skapats är följande:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
Noden med data 10 raderas från listan
Cirkulär länkad lista efter radering av 10 är som följer:
20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 20
Därefter presenterar vi en Java-implementering för de cirkulära länkoperationerna.
//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); } } Produktion:
Cirkulär länkad lista skapad är:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
Efter radering av 40 är den cirkulära listan:
10 ==> 20 ==> 30 ==> 50 ==> 60 ==> 10
Fördelar / nackdelar
Låt oss diskutera några fördelar och nackdelar med den cirkulära länken.
Fördelar:
- Vi kan gå till vilken nod som helst och korsa från vilken nod som helst. Vi behöver bara sluta när vi besöker samma nod igen.
- Eftersom den sista noden pekar på den första noden tar det bara ett steg att gå till den första noden från den sista noden.
Nackdelar:
- Att vända en cirkulär länkad lista är besvärlig.
- Eftersom noderna är anslutna för att bilda en cirkel finns det ingen korrekt markering för början eller slutet för listan. Därför är det svårt att hitta slutet på listan eller loopkontrollen. Om det inte tas hand om kan en implementering hamna i en oändlig slinga.
- Vi kan inte gå tillbaka till den föregående noden i ett enda steg. Vi måste gå igenom hela listan från början.
Tillämpningar av cirkulär länkad lista
- Realtidstillämpning av cirkulär länkad lista kan vara ett operativsystem med flera programmeringar där det schemalägger flera program. Varje program ges en särskild tidsstämpel att utföra, varefter resurserna skickas till ett annat program. Detta fortsätter kontinuerligt under en cykel. Denna representation kan effektivt uppnås med hjälp av en cirkulär länkad lista.
- Spel som spelas med flera spelare kan också representeras med hjälp av en cirkulär länkad lista där varje spelare är en nod som ges en chans att spela.
- Vi kan använda en cirkulär länkad lista för att representera en cirkulär kö. Genom att göra detta kan vi ta bort de två pekarna fram och bak som används för kön. Istället kan vi bara använda en pekare.
Slutsats
En cirkulär länkad lista är en samling noder där noder är anslutna till varandra för att bilda en cirkel. Detta innebär att istället för att ställa in nästa pekare för den sista noden till null, är den länkad till den första noden.
En cirkulär länkad lista hjälper till att representera strukturer eller aktiviteter som måste upprepas om och om igen efter ett specifikt tidsintervall, t.ex. program i en multiprogrammeringsmiljö. Det är också fördelaktigt för att utforma en cirkulär kö.
Cirkulära länkade listor stöder olika operationer som insättning, radering och traversaler. Således har vi sett operationerna i detalj i denna handledning.
I vårt nästa ämne om datastrukturer lär vi oss om stackdatastrukturen.
=> Kolla här för att se A-Z av C ++ träningstutorialer här.
Rekommenderad läsning
- Länkad listdatastruktur i C ++ med illustration
- Dubbel länkad datastruktur i C ++ med illustration
- Kodatastruktur i C ++ med illustration
- Stack datastruktur i C ++ med illustration
- Prioriterad köstruktur i C ++ med illustration
- Topp 15 bästa gratis datavärvningsverktyg: den mest omfattande listan
- Introduktion till datastrukturer i C ++
- 15 bästa ETL-verktyg 2021 (en fullständig uppdaterad lista)