Meniu

Structură de date cu listă circulară legată în C ++ cu ilustrație

  • Principal
  • Alte
  • Structură de date cu listă circulară legată în C ++ cu ilustrație

circular linked list data structure c with illustration

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

O prezentare completă a listei circulare legate.

O listă circulară legată este o variantă a listei conectate. Este o listă legată ale cărei noduri sunt conectate în așa fel încât formează un cerc.

În lista circulară legată, următorul indicator al ultimului nod nu este setat la nul, dar conține adresa primului nod formând astfel un cerc.

=> Vizitați aici pentru a afla C ++ de la zero.

Listă circulară legată

Ce veți învăța:

Listă circulară legată în C ++

Aranjamentul prezentat mai jos este pentru o listă legată individual.

listă legată individual

O listă circulară legată poate fi o listă legată individual sau o listă dublă legată. Într-o listă legată dublu circular, indicatorul anterior al primului nod este conectat la ultimul nod, în timp ce următorul indicator al ultimului nod este conectat la primul nod.

Reprezentarea sa este prezentată mai jos.

listă legată dublu circular

Declaraţie

Putem declara un nod într-o listă circulară legată ca orice alt nod așa cum se arată mai jos:

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

Pentru a implementa lista circulară legată, menținem un pointer extern „ultimul” care indică ultimul nod din lista circulară legată. Prin urmare, last-> next va indica primul nod din lista legată.

Procedând astfel, ne asigurăm că atunci când introducem un nou nod la începutul sau la sfârșitul listei, nu trebuie să traversăm întreaga listă. Acest lucru se datorează faptului că ultimul punct către ultimul nod în timp ce ultimul -> următorul punct către primul nod.

Acest lucru nu ar fi fost posibil dacă am fi îndreptat indicatorul extern către primul nod.

Operațiuni de bază

Lista circulară legată acceptă inserarea, ștergerea și traversarea listei. Vom discuta în detaliu fiecare dintre operațiuni acum.

Inserare

Putem insera un nod într-o listă circulară legată fie ca prim nod (listă goală), la început, la sfârșit sau între celelalte noduri. Să vedem fiecare dintre aceste operații de inserare folosind o reprezentare picturală de mai jos.

# 1) Introduceți într-o listă goală

Introduceți într-o listă goală

Când nu există noduri în lista circulară și lista este goală, ultimul indicator este nul, apoi introducem un nou nod N îndreptând ultimul indicator către nodul N așa cum se arată mai sus. Următorul indicator al lui N va indica nodul N în sine, deoarece există un singur nod. Astfel, N devine primul și ultimul nod din listă.

# 2) Inserați la începutul listei

Introduceți la începutul listei

Așa cum se arată în reprezentarea de mai sus, atunci când adăugăm un nod la începutul listei, următorul indicator al ultimului nod indică noul nod N, făcându-l astfel un prim nod.

N-> următor = ultim-> următor

Last-> next = N

# 3) Introduceți la sfârșitul listei

ultimul nod indică noul nod

Pentru a insera un nou nod la sfârșitul listei, urmăm acești pași:

deschiderea fișierelor jar pe Windows 10

N-> următor = ultim -> următor;
ultimul -> următorul = N
ultimul = N

# 4) Inserați între listă

Introduceți între listă

Să presupunem că trebuie să inserăm un nou nod N între N3 și N4, trebuie mai întâi să traversăm lista și să localizăm nodul după care noul nod trebuie să fie inserat, în acest caz, N3-ul său.

După localizarea nodului, efectuăm pașii următori.

N -> următor = N3 -> următor;
N3 -> următor = N

Aceasta introduce un nou nod N după N3.

Ștergere

Operațiunea de ștergere a listei circulare legate implică localizarea nodului care urmează să fie șters și apoi eliberarea memoriei acestuia.

Pentru aceasta menținem doi indicatori suplimentari curr și prev și apoi traversăm lista pentru a localiza nodul. Nodul dat de șters poate fi primul nod, ultimul nod sau nodul dintre ele. În funcție de locație, setăm indicatorii curr și prev și apoi ștergem nodul curr.

O reprezentare picturală a operației de ștergere este prezentată mai jos.

operațiunea de ștergere

Traversal

Traversal este o tehnică de vizitare a fiecărui nod. În listele cu legături liniare, cum ar fi lista cu legături individuale și listele cu legături duble, traversarea este ușoară pe măsură ce vizităm fiecare nod și ne oprim când este întâlnit NULL.

Cu toate acestea, acest lucru nu este posibil într-o listă circulară legată. Într-o listă circulară legată, începem de la următorul ultim nod care este primul nod și traversăm fiecare nod. Ne oprim când ajungem din nou la primul nod.

Acum prezentăm o implementare a operațiunilor de listă circulară legată folosind C ++ și Java. Aici am implementat operațiuni de inserare, ștergere și traversare. Pentru o înțelegere clară, am descris lista circulară legată ca

Traversal

Astfel, la ultimul nod 50, atașăm din nou nodul 10 care este primul nod, indicându-l astfel ca o listă circulară legată.

#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 '<

Ieșire:

Lista circulară legată creată este după cum urmează:

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

Nodul cu date 10 este șters din listă

Lista circulară legată după ștergerea 10 este următoarea:

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

În continuare, vă prezentăm o implementare Java pentru operațiunile cu listă circulară.

//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); } }

Ieșire:

Lista circulară legată creată este:

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

După ștergerea 40, lista circulară este:

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

Avantaje dezavantaje

Să discutăm câteva avantaje și dezavantaje ale listei circulare legate.

Avantaje:

  • Putem merge la orice nod și să traversăm din orice nod. Trebuie doar să ne oprim când vizităm din nou același nod.
  • Pe măsură ce ultimul nod indică primul nod, mergi la primul nod de la ultimul nod face doar un singur pas.

Dezavantaje:

  • Inversarea unei liste circulare legate este greoaie.
  • Deoarece nodurile sunt conectate pentru a forma un cerc, nu există o marcare adecvată pentru început sau sfârșit pentru listă. Prin urmare, este dificil să găsiți sfârșitul listei sau controlul buclei. Dacă nu este îngrijită, o implementare ar putea ajunge într-o buclă infinită.
  • Nu putem reveni la nodul anterior într-un singur pas. Trebuie să traversăm întreaga listă de la început.

Aplicații ale listei circulare legate

  • Aplicarea în timp real a listei circulare conectate poate fi un sistem de operare multi-programare în care programează mai multe programe. Fiecărui program i se acordă un timestamp dedicat de executat, după care resursele sunt transmise unui alt program. Acest lucru continuă într-un ciclu. Această reprezentare poate fi realizată eficient utilizând o listă circulară legată.
  • Jocurile care se joacă cu mai mulți jucători pot fi, de asemenea, reprezentate folosind o listă circulară legată în care fiecare jucător este un nod căruia i se oferă șansa de a juca.
  • Putem folosi o listă circulară legată pentru a reprezenta o coadă circulară. Procedând astfel, putem elimina cele două indicatoare din față și din spate care sunt utilizate pentru coadă. În schimb, putem folosi un singur indicator.

Concluzie

O listă circulară legată este o colecție de noduri în care nodurile sunt conectate între ele pentru a forma un cerc. Aceasta înseamnă că, în loc să setați următorul indicator al ultimului nod la nul, este legat de primul nod.

O listă circulară legată este utilă în reprezentarea structurilor sau activităților care trebuie repetate din nou și din nou după un anumit interval de timp, cum ar fi programele dintr-un mediu multiprogramare. De asemenea, este benefic pentru proiectarea unei cozi circulare.

Listele circulare conectate acceptă diverse operații, cum ar fi inserarea, ștergerea și traversările. Astfel, am văzut operațiunile în detaliu în acest tutorial.

În următorul nostru subiect despre structurile de date, vom afla despre structura de date a stivei.

=> Verificați aici pentru a vedea A-Z a tutorialelor de formare C ++ aici.

Lectură recomandată

^