circular linked list data structure c with illustration
Una panoramica completa dell'elenco collegato circolare.
Un elenco collegato circolare è una variazione dell'elenco collegato. È un elenco collegato i cui nodi sono collegati in modo tale da formare un cerchio.
Nella lista concatenata circolare, il puntatore successivo dell'ultimo nodo non è impostato a null ma contiene l'indirizzo del primo nodo formando così un cerchio.
=> Visita qui per imparare C ++ da zero.
Cosa imparerai:
Elenco collegato circolare in C ++
La disposizione mostrata di seguito è per un elenco collegato singolarmente.
Un elenco collegato circolare può essere un elenco collegato singolarmente o un elenco collegato doppiamente. In una lista concatenata doppiamente circolare, il puntatore precedente del primo nodo è connesso all'ultimo nodo mentre il puntatore successivo dell'ultimo nodo è connesso al primo nodo.
La sua rappresentazione è mostrata di seguito.
Dichiarazione
Possiamo dichiarare un nodo in un elenco collegato circolare come qualsiasi altro nodo come mostrato di seguito:
struct Node { int data; struct Node *next; }; Per implementare la lista collegata circolare, manteniamo un puntatore esterno 'last' che punta all'ultimo nodo della lista collegata circolare. Quindi last-> next punterà al primo nodo nell'elenco collegato.
In questo modo ci assicuriamo che quando inseriamo un nuovo nodo all'inizio o alla fine della lista, non abbiamo bisogno di attraversare l'intera lista. Questo perché l'ultimo punta all'ultimo nodo mentre last-> next punta al primo nodo.
Questo non sarebbe stato possibile se avessimo puntato il puntatore esterno al primo nodo.
Operazioni di base
L'elenco collegato circolare supporta l'inserimento, l'eliminazione e l'attraversamento dell'elenco. Discuteremo ora ciascuna delle operazioni in dettaglio.
Inserimento
Possiamo inserire un nodo in una lista circolare collegata o come primo nodo (lista vuota), all'inizio, alla fine o tra gli altri nodi. Vediamo ciascuna di queste operazioni di inserimento utilizzando una rappresentazione pittorica di seguito.
# 1) Inserisci in un elenco vuoto
Quando non ci sono nodi nella lista circolare e la lista è vuota, l'ultimo puntatore è nullo, quindi inseriamo un nuovo nodo N puntando l'ultimo puntatore al nodo N come mostrato sopra. Il prossimo puntatore di N punterà al nodo N stesso poiché esiste un solo nodo. Quindi N diventa il primo e l'ultimo nodo nell'elenco.
# 2) Inserisci all'inizio della lista
Come mostrato nella rappresentazione sopra, quando aggiungiamo un nodo all'inizio della lista, il puntatore successivo dell'ultimo nodo punta al nuovo nodo N rendendolo così un primo nodo.
N-> successivo = ultimo-> successivo
Ultimo-> successivo = N
# 3) Inserisci alla fine della lista
Per inserire un nuovo nodo alla fine della lista, seguiamo questi passaggi:
domande e risposte dell'intervista del server sql per esperti con esempi
N-> successivo = ultimo -> successivo;
ultimo -> successivo = N
ultimo = N
# 4) Inserisci tra l'elenco
Supponiamo di dover inserire un nuovo nodo N tra N3 e N4, dobbiamo prima attraversare la lista e individuare il nodo dopo il quale va inserito il nuovo nodo, in questo caso il suo N3.
Dopo aver individuato il nodo, eseguiamo i seguenti passaggi.
N -> successivo = N3 -> successivo;
N3 -> successivo = N
Questo inserisce un nuovo nodo N dopo N3.
Cancellazione
L'operazione di cancellazione della lista collegata circolare prevede l'individuazione del nodo da cancellare e quindi la liberazione della sua memoria.
Per questo manteniamo due puntatori aggiuntivi curr e prev e quindi attraversiamo l'elenco per individuare il nodo. Il nodo specificato da eliminare può essere il primo nodo, l'ultimo nodo o il nodo intermedio. A seconda della posizione, impostiamo i puntatori curr e prev e quindi cancelliamo il nodo curr.
Di seguito è mostrata una rappresentazione grafica dell'operazione di cancellazione.
Traversal
Traversal è una tecnica per visitare ogni singolo nodo. Negli elenchi concatenati lineari come gli elenchi concatenati singolarmente e gli elenchi concatenati doppiamente, l'attraversamento è facile poiché visitiamo ogni nodo e ci fermiamo quando si incontra NULL.
Tuttavia, ciò non è possibile in un elenco collegato circolare. In un elenco collegato circolare, partiamo dal successivo dell'ultimo nodo che è il primo nodo e attraversiamo ogni nodo. Ci fermiamo quando raggiungiamo nuovamente il primo nodo.
Ora presentiamo un'implementazione delle operazioni di elenchi concatenati circolari utilizzando C ++ e Java. Abbiamo implementato le operazioni di inserimento, cancellazione e attraversamento qui. Per una chiara comprensione, abbiamo rappresentato l'elenco collegato circolare come
Pertanto, all'ultimo nodo 50, colleghiamo nuovamente il nodo 10 che è il primo nodo, indicandolo in tal modo come una lista concatenata circolare.
#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 '< Produzione:
L'elenco collegato circolare creato è il seguente:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
Il nodo con i dati 10 viene eliminato dall'elenco
L'elenco collegato circolare dopo l'eliminazione di 10 è il seguente:
20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 20
Successivamente, presentiamo un'implementazione Java per le operazioni di elenchi collegati circolari.
//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); } } Produzione:
L'elenco collegato circolare creato è:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
Dopo aver cancellato 40 l'elenco circolare è:
10 ==> 20 ==> 30 ==> 50 ==> 60 ==> 10
Vantaggi e svantaggi
Discutiamo alcuni vantaggi e svantaggi dell'elenco collegato circolare.
Vantaggi:
- Possiamo andare a qualsiasi nodo e attraversare da qualsiasi nodo. Dobbiamo solo fermarci quando visiteremo di nuovo lo stesso nodo.
- Poiché l'ultimo nodo punta al primo nodo, andare al primo nodo dall'ultimo nodo richiede solo un singolo passaggio.
Svantaggi:
- Invertire un elenco collegato circolare è macchinoso.
- Poiché i nodi sono collegati per formare un cerchio, non esiste un contrassegno appropriato per l'inizio o la fine dell'elenco. Pertanto, è difficile trovare la fine dell'elenco o il controllo del ciclo. Se non viene prestata attenzione, un'implementazione potrebbe finire in un ciclo infinito.
- Non possiamo tornare al nodo precedente in un solo passaggio. Dobbiamo attraversare l'intera lista dall'inizio.
Applicazioni della lista collegata circolare
- L'applicazione in tempo reale dell'elenco collegato circolare può essere un sistema operativo multi-programmazione in cui pianifica più programmi. Ad ogni programma viene assegnato un timestamp dedicato da eseguire, dopodiché le risorse vengono passate a un altro programma. Questo va avanti continuamente in un ciclo. Questa rappresentazione può essere ottenuta in modo efficiente utilizzando un elenco collegato circolare.
- I giochi che vengono giocati con più giocatori possono anche essere rappresentati utilizzando un elenco collegato circolare in cui ogni giocatore è un nodo a cui viene data la possibilità di giocare.
- Possiamo usare un elenco collegato circolare per rappresentare una coda circolare. In questo modo, possiamo rimuovere i due puntatori anteriore e posteriore utilizzati per la coda. Invece, possiamo usare un solo puntatore.
Conclusione
Un elenco collegato circolare è una raccolta di nodi in cui i nodi sono collegati tra loro per formare un cerchio. Ciò significa che invece di impostare il puntatore successivo dell'ultimo nodo su null, è collegato al primo nodo.
Un elenco collegato circolare è utile per rappresentare strutture o attività che devono essere ripetute più e più volte dopo un intervallo di tempo specifico come i programmi in un ambiente multiprogrammazione. È anche utile per progettare una coda circolare.
Gli elenchi collegati circolari supportano varie operazioni come l'inserimento, l'eliminazione e gli attraversamenti. Quindi abbiamo visto le operazioni in dettaglio in questo tutorial.
Nel prossimo argomento sulle strutture dei dati, impareremo la struttura dei dati dello stack.
=> Controlla qui per vedere i tutorial di formazione dalla A alla Z di C ++ qui.
Lettura consigliata
- Struttura Dati Elenco Collegato In C ++ Con Illustrazione
- Struttura dei dati della lista doppiamente collegata in C ++ con illustrazione
- Struttura dei dati della coda in C ++ con illustrazione
- Stack Struttura Dati In C ++ Con Illustrazione
- Priorità Struttura Dati Coda In C ++ Con Illustrazione
- I 15 migliori strumenti gratuiti per il data mining: l'elenco più completo
- Introduzione alle strutture dati in C ++
- 15 migliori strumenti ETL nel 2021 (un elenco aggiornato completo)