circular linked list data structure c with illustration
Una visió completa de la llista enllaçada circular.
Una llista enllaçada circular és una variació de la llista enllaçada. És una llista enllaçada els nodes de la qual estan connectats de manera que forma un cercle.
A la llista enllaçada circular, el següent punter de l'últim node no està definit com a nul, però conté l'adreça del primer node formant així un cercle.
=> Visiteu aquí per aprendre C ++ des de zero.
Què aprendreu:
Llista circular enllaçada a C ++
La disposició que es mostra a continuació és per a una llista enllaçada individualment.
Una llista enllaçada circular pot ser una llista enllaçada individualment o una llista doblement enllaçada. En una llista enllaçada doblement circular, el punter anterior del primer node està connectat a l'últim node mentre que el següent punter de l'últim node està connectat al primer node.
La seva representació es mostra a continuació.
Declaració
Podem declarar un node en una llista enllaçada circular com qualsevol altre node, tal com es mostra a continuació:
struct Node { int data; struct Node *next; }; Per implementar la llista enllaçada circular, mantenim un punter extern 'darrer' que apunta al darrer node de la llista enllaçada circular. Per tant, last-> next apuntarà al primer node de la llista enllaçada.
En fer-ho, ens assegurem que quan inserim un nou node al principi o al final de la llista, no necessitem recórrer tota la llista. Això es deu al fet que l'últim apunta al darrer node mentre que l'últim-> següent apunta al primer node.
Això no hauria estat possible si haguéssim apuntat el punter extern al primer node.
Operacions bàsiques
La llista enllaçada circular admet la inserció, supressió i recorregut de la llista. Ara analitzarem detalladament cadascuna de les operacions.
Inserció
Podem inserir un node en una llista enllaçada circular com a primer node (llista buida), al principi, al final o entre els altres nodes. Vegem cadascuna d’aquestes operacions d’inserció mitjançant una representació pictòrica a continuació.
# 1) Insereix en una llista buida
Quan no hi ha nodes a la llista circular i la llista està buida, l'últim punter és nul, i llavors inserim un nou node N assenyalant l'últim punter cap al node N com es mostra a la part superior. El següent punter de N assenyalarà el propi node N ja que només hi ha un node. Així, N esdevé el primer i el darrer node de la llista.
# 2) Insereix al principi de la llista
Com es mostra a la representació anterior, quan afegim un node al començament de la llista, el següent punter de l'últim node assenyala el nou node N, convertint-lo en un primer node.
N-> següent = últim-> següent
Darrer-> següent = N
# 3) Inseriu al final de la llista
Per inserir un nou node al final de la llista, seguim aquests passos:
aplicació de targeta de temps per a iPhone i Android
N-> següent = últim -> següent;
darrer -> següent = N
darrer = N
# 4) Inseriu entre la llista
Suposem que hem d’inserir un nou node N entre N3 i N4, primer hem de recórrer la llista i localitzar el node després del qual s’ha d’inserir el nou node, en aquest cas, el seu N3.
Després de localitzar el node, realitzem els passos següents.
N -> següent = N3 -> següent;
N3 -> següent = N
Això insereix un nou node N després de N3.
Supressió
L'operació de supressió de la llista enllaçada circular consisteix a localitzar el node que s'ha de suprimir i després alliberar-ne la memòria.
Per a això mantenim dos punters addicionals curr i prev i després recorrem la llista per localitzar el node. El node que es vol esborrar pot ser el primer node, l'últim node o el node intermedi. Depenent de la ubicació, definim els indicadors curr i prev i, a continuació, suprimim el node curr.
A continuació es mostra una representació pictòrica de l’operació de supressió.
Transversal
El transversal és una tècnica per visitar tots i cadascun dels nodes. A les llistes enllaçades lineals, com ara llistes enllaçades individualment i llistes doblement enllaçades, la travessia és fàcil ja que visitem cada node i parem quan es troba NULL.
Tot i això, això no és possible en una llista enllaçada circular. En una llista enllaçada circular, comencem pel següent de l'últim node que és el primer node i recorrem cada node. Ens aturem quan arribem de nou al primer node.
Ara presentem una implementació de les operacions de llista enllaçada circular mitjançant C ++ i Java. Aquí hem implementat operacions d’inserció, supressió i recorregut. Per a una comprensió clara, hem representat la llista enllaçada circular com
Així, a l'últim node 50, tornem a adjuntar el node 10, que és el primer node, indicant-lo així com una llista enllaçada circular.
#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 '< Sortida:
La llista circular enllaçada creada és la següent:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
El node amb dades 10 se suprimeix de la llista
La llista enllaçada circular després de suprimir 10 és la següent:
20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 20
A continuació, presentem una implementació de Java per a les operacions de llista enllaçada 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); } } Sortida:
La llista d'enllaços circulars creada és:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
Després de suprimir 40, la llista circular és:
10 ==> 20 ==> 30 ==> 50 ==> 60 ==> 10
Avantatges / Desavantatges
Analitzem alguns avantatges i desavantatges de la llista enllaçada circular.
Avantatges:
- Podem anar a qualsevol node i recórrer-lo des de qualsevol node. Només hem de parar quan tornem a visitar el mateix node.
- A mesura que l'últim node apunta al primer node, anar al primer node de l'últim node només fa un sol pas.
Desavantatges:
- Invertir una llista enllaçada circular és complicat.
- Com que els nodes estan connectats per formar un cercle, no hi ha cap marcatge adequat per a l'inici o el final de la llista. Per tant, és difícil trobar el final de la llista o el control de bucle. Si no es té cura, una implementació pot acabar en un bucle infinit.
- No podem tornar al node anterior en un sol pas. Hem de recórrer tota la llista des del primer moment.
Aplicacions de la llista enllaçada circular
- L’aplicació en temps real de la llista enllaçada circular pot ser un sistema operatiu de programació múltiple en el qual programa diversos programes. A cada programa se li proporciona una marca de temps dedicada per executar, després de la qual cosa els recursos es passen a un altre programa. Això continua contínuament en un cicle. Aquesta representació es pot aconseguir eficientment mitjançant una llista enllaçada circular.
- Els jocs que es juguen amb diversos jugadors també es poden representar mitjançant una llista enllaçada circular en què cada jugador és un node que té l'oportunitat de jugar.
- Podem utilitzar una llista enllaçada circular per representar una cua circular. Fent això, podem eliminar els dos punteres davanters i posteriors que s’utilitzen per a la cua. En canvi, només podem utilitzar un punter.
Conclusió
Una llista enllaçada circular és una col·lecció de nodes en què els nodes es connecten entre si per formar un cercle. Això significa que, en lloc de configurar el següent punter de l'últim node a null, s'enllaça amb el primer node.
Una llista enllaçada circular és útil per representar estructures o activitats que cal repetir una i altra vegada després d’un interval de temps específic, com ara els programes en un entorn de multiprogramació. També és beneficiós per dissenyar una cua circular.
Les llistes enllaçades circulars admeten diverses operacions com ara inserció, supressió i recorreguts. Així, hem vist les operacions amb detall en aquest tutorial.
Al següent tema sobre les estructures de dades, coneixerem l’estructura de dades de la pila.
=> Consulteu aquí per veure aquí els tutorials de formació A-Z de C ++.
Lectura recomanada
- Estructura de dades de la llista enllaçada en C ++ amb il·lustració
- Estructura de dades de llistes doblement enllaçades en C ++ amb il·lustració
- Estructura de dades de la cua en C ++ amb il·lustració
- Estructura de dades de pila en C ++ amb il·lustració
- Estructura de dades de la cua de prioritat en C ++ amb il·lustració
- Top 15 de les millors eines gratuïtes de mineria de dades: la llista més completa
- Introducció a les estructures de dades en C ++
- 15 millors eines ETL el 2021 (llista completa actualitzada)