Menu

Cirkulær sammenkædet liste Datastruktur i C ++ med illustration

  • Vigtigste
  • Andet
  • Cirkulær sammenkædet liste Datastruktur i C ++ med illustration

circular linked list data structure c with illustration

Prøv Vores Instrument Til At Fjerne Problemer

En komplet oversigt over cirkulær sammenkædningsliste.

En cirkulær sammenkædet liste er en variation af den sammenkædede liste. Det er en sammenkædet liste, hvis noder er forbundet på en sådan måde, at den danner en cirkel.

På den cirkulære sammenkædede liste er den næste markør for den sidste node ikke sat til null, men den indeholder adressen på den første node og danner således en cirkel.

=> Besøg her for at lære C ++ fra bunden.

Cirkulær linket liste

Hvad du lærer:

Cirkulær sammenkædet liste i C ++

Arrangementet vist nedenfor er for en enkelt linket liste.

enkeltkædet liste

En cirkulær sammenkædet liste kan være en enkeltkædet liste eller en dobbeltkædet liste. I en dobbelt cirkulær sammenkædet liste er den forrige markør for den første node forbundet med den sidste node, mens den næste markør for den sidste node er forbundet med den første node.

Dens repræsentation er vist nedenfor.

dobbelt cirkulær sammenkædet liste

Erklæring

Vi kan erklære en node i en cirkulær sammenkædet liste som enhver anden node som vist nedenfor:

struct Node { int data; struct Node *next; };

For at implementere den cirkulærkædede liste opretholder vi en ekstern markør “sidste”, der peger på den sidste knude i den cirkulærkædede liste. Derfor vil sidste-> næste pege på den første node i den linkede liste.

Ved at gøre dette sikrer vi, at når vi indsætter en ny node i starten eller slutningen af ​​listen, behøver vi ikke krydse hele listen. Dette skyldes, at de sidste peger på den sidste knude, mens sidste-> næste peger på den første knude.

Dette ville ikke have været muligt, hvis vi havde peget den eksterne markør på den første knude.

Grundlæggende funktioner

Den cirkulære sammenkædede liste understøtter indsættelse, sletning og gennemkørsel af listen. Vi vil diskutere hver af operationerne detaljeret nu.

Indskud

Vi kan indsætte en node i en cirkulær sammenkædet liste enten som en første node (tom liste), i begyndelsen, i slutningen eller mellem de andre noder. Lad os se hver af disse indsættelsesoperationer ved hjælp af en billedrepræsentation nedenfor.

# 1) Indsæt i en tom liste

Indsæt i en tom liste

Når der ikke er nogen noder i den cirkulære liste, og listen er tom, er den sidste markør nul, så indsætter vi en ny node N ved at pege den sidste markør på noden N som vist ovenfor. Den næste markør af N vil pege på selve noden N, da der kun er en node. Således bliver N den første såvel som den sidste knude på listen.

# 2) Indsæt i begyndelsen af ​​listen

Indsæt i begyndelsen af ​​listen

Som vist i ovenstående repræsentation, når vi tilføjer en node i begyndelsen af ​​listen, peger den næste markør i den sidste node til den nye node N og derved gør den til en første node.

N-> næste = sidste-> næste

Sidste-> næste = N

# 3) Indsæt i slutningen af ​​listen

sidste node peger på den nye node

For at indsætte en ny knude i slutningen af ​​listen følger vi disse trin:

netværksingeniør interview spørgsmål og svar i cisco

N-> næste = sidste -> næste;
sidste -> næste = N
sidste = N

# 4) Indsæt mellem listen

Indsæt mellem listen

Antag, at vi har brug for at indsætte en ny node N mellem N3 og N4, skal vi først krydse listen og finde den node, hvorefter den nye node skal indsættes, i dette tilfælde dens N3.

Når noden er placeret, udfører vi følgende trin.

N -> næste = N3 -> næste;
N3 -> næste = N

Dette indsætter en ny node N efter N3.

Sletning

Sletningsoperationen af ​​den cirkulærkædede liste indebærer lokalisering af den node, der skal slettes, og derefter frigøres hukommelsen.

Til dette opretholder vi to yderligere markører curr og prev og krydser derefter listen for at lokalisere noden. Den givne knude, der skal slettes, kan være den første knude, den sidste knude eller noden derimellem. Afhængigt af placeringen indstiller vi curr og forrige markører og sletter derefter curr node.

En billedlig gengivelse af sletningsoperationen er vist nedenfor.

sletning

Traversal

Traversal er en teknik til at besøge hver eneste knude. I lineære sammenkædede lister som enkeltkædet liste og dobbeltkædede lister er det let at krydse, når vi besøger hver knude og stopper, når der opstår NULL.

Dette er dog ikke muligt i en cirkulær sammenkædet liste. I en cirkulær sammenkædet liste starter vi fra den næste af den sidste node, som er den første node og krydser hver node. Vi stopper, når vi igen når den første knude.

Nu præsenterer vi en implementering af de cirkulære sammenkædede listeoperationer ved hjælp af C ++ og Java. Vi har implementeret indsættelse, sletning og traversal operationer her. For en klar forståelse har vi afbildet den cirkulære sammenkædede liste som

Traversal

Således til den sidste knudepunkt 50 vedhæfter vi igen knudepunkt 10, som er den første knudepunkt, hvorved det angives som en cirkulær sammenkædet liste.

#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 oprettede cirkulære sammenkædede liste er som følger:

10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10

Noden med data 10 slettes fra listen

Den cirkulære sammenkædede liste efter sletning af 10 er som følger:

20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 20

Dernæst præsenterer vi en Java-implementering til Circular linked-lister.

//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:

Den cirkulære linkede liste er oprettet:

10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10

Efter at have slettet 40 er den cirkulære liste:

10 ==> 20 ==> 30 ==> 50 ==> 60 ==> 10

Fordele ulemper

Lad os diskutere nogle fordele og ulemper ved den cirkulære sammenkædede liste.

Fordele:

  • Vi kan gå til enhver knude og krydse fra enhver knude. Vi skal bare stoppe, når vi besøger den samme knude igen.
  • Da den sidste node peger på den første node, tager det kun et enkelt trin at gå til den første node fra den sidste node.

Ulemper:

  • Det er besværligt at vende en cirkulær sammenkædet liste.
  • Da knudepunkterne er forbundet for at danne en cirkel, er der ingen korrekt markering for begyndelsen eller slutningen af ​​listen. Derfor er det vanskeligt at finde slutningen af ​​listen eller loopkontrol. Hvis det ikke bliver taget hånd om, kan en implementering ende i en uendelig løkke.
  • Vi kan ikke gå tilbage til den forrige node i et enkelt trin. Vi er nødt til at krydse hele listen fra først.

Anvendelser af cirkulær sammenkædet liste

  • Realtidsanvendelse af cirkulær sammenkædet liste kan være et multi-programmerings-operativsystem, hvor det planlægger flere programmer. Hvert program får et dedikeret tidsstempel, der skal udføres, hvorefter ressourcerne overføres til et andet program. Dette fortsætter kontinuerligt i en cyklus. Denne repræsentation kan opnås effektivt ved hjælp af en cirkulær sammenkædet liste.
  • Spil, der spilles med flere spillere, kan også repræsenteres ved hjælp af en cirkulær sammenkædet liste, hvor hver spiller er en node, der får en chance for at spille.
  • Vi kan bruge en cirkulær sammenkædet liste til at repræsentere en cirkulær kø. Ved at gøre dette kan vi fjerne de to markører foran og bag, der bruges til køen. I stedet kan vi kun bruge en markør.

Konklusion

En cirkulær sammenkædet liste er en samling noder, hvor noder er forbundet med hinanden for at danne en cirkel. Dette betyder i stedet for at indstille den næste markør til den sidste node til null, den er knyttet til den første node.

En cirkulær sammenkædet liste er nyttig til at repræsentere strukturer eller aktiviteter, der skal gentages igen og igen efter et specifikt tidsinterval som programmer i et multiprogrammeringsmiljø. Det er også en fordel at designe en cirkulær kø.

Cirkelforbundne lister understøtter forskellige operationer som indsættelse, sletning og traversaler. Således har vi set operationerne detaljeret i denne vejledning.

I vores næste emne om datastrukturer vil vi lære om stakdatastrukturen.

=> Tjek her for at se AZ af C ++ træningsvejledninger her.

Anbefalet læsning

^