Elenco collegato circolare: vantaggi con l'esempio di programma C.

Sommario:

Anonim

Cos'è un elenco collegato circolare?

Un elenco collegato circolare è una sequenza di nodi disposti in modo tale che ogni nodo possa essere ricondotto a se stesso. Qui un "nodo" è un elemento autoreferenziale con puntatori a uno o due nodi nelle immediate vicinanze di iI.

Di seguito è riportata una rappresentazione di un elenco collegato circolare con 3 nodi.

Qui puoi vedere che ogni nodo è retrattile a se stesso. L'esempio mostrato sopra è un elenco circolare collegato singolarmente.

Nota: la più semplice lista circolare collegata è un nodo che traccia solo su se stesso come mostrato

In questo tutorial sull'elenco collegato circolare, imparerai:

  • Cos'è un elenco collegato circolare?
  • Operazioni di base
  • Operazione di inserimento
  • Operazione di cancellazione
  • Attraversamento di un elenco collegato circolare
  • Vantaggi dell'elenco collegato circolare
  • Elenco collegato singolarmente come elenco collegato circolare
  • Applicazioni della lista collegata circolare

Operazioni di base

Le operazioni di base su un elenco collegato circolare sono:

  1. Inserimento
  2. Cancellazione e
  3. Traversal
  • L'inserimento è il processo di posizionamento di un nodo in una posizione specificata nell'elenco collegato circolare.
  • L'eliminazione è il processo di rimozione di un nodo esistente dall'elenco collegato. Il nodo può essere identificato dall'occorrenza del suo valore o dalla sua posizione.
  • L'attraversamento di un elenco collegato circolare è il processo di visualizzazione dell'intero contenuto dell'elenco collegato e del ritorno al nodo di origine.

Nella sezione successiva, capirai l'inserimento di un nodo e i tipi di inserimento possibili in un elenco circolare collegato singolarmente.

Operazione di inserimento

Inizialmente, è necessario creare un nodo che punti a se stesso come mostrato in questa immagine. Senza questo nodo, l'inserimento crea il primo nodo.

Successivamente, ci sono due possibilità:

  • Inserimento nella posizione corrente della lista collegata circolare. Ciò corrisponde all'inserimento all'inizio della fine di una lista concatenata singolare regolare. In un elenco collegato circolare, l'inizio e la fine sono gli stessi.
  • Inserimento dopo un nodo indicizzato. Il nodo dovrebbe essere identificato da un numero di indice corrispondente al valore del suo elemento.

Per l'inserimento all'inizio / alla fine della lista collegata circolare, cioè nella posizione in cui è stato aggiunto il primo nodo in assoluto,

  • Dovrai interrompere l'auto-collegamento esistente al nodo esistente
  • Il prossimo puntatore del nuovo nodo si collegherà al nodo esistente.
  • Il prossimo puntatore dell'ultimo nodo punterà al nodo inserito.

NOTA: il puntatore che è il token master o l'inizio / fine del cerchio può essere modificato. Tornerà comunque allo stesso nodo durante un attraversamento, discusso in seguito.

I passaggi in (a) i-iii sono mostrati di seguito:

(Nodo esistente)

PASSAGGIO 1) Rompere il collegamento esistente

PASSAGGIO 2) Creare un collegamento in avanti (dal nuovo nodo a un nodo esistente)

PASSAGGIO 3) Creare un collegamento loop al primo nodo

Successivamente, proverai l'inserimento dopo un nodo.

Ad esempio, inseriamo "VALUE2" dopo il nodo con "VALUE0". Supponiamo che il punto di partenza sia il nodo con "VALUE0".

  • Dovrai interrompere la linea tra il primo e il secondo nodo e posizionare il nodo con "VALUE2" in mezzo.
  • Il puntatore successivo del primo nodo deve collegarsi a questo nodo e il puntatore successivo di questo nodo deve collegarsi al secondo nodo precedente.
  • Il resto della disposizione rimane invariato. Tutti i nodi sono rintracciabili a se stessi.

NOTA: poiché esiste una disposizione ciclica, l'inserimento di un nodo comporta la stessa procedura per qualsiasi nodo. Il puntatore che completa un ciclo completa il ciclo proprio come qualsiasi altro nodo.

Questo è mostrato di seguito:

(Diciamo che ci sono solo due nodi. Questo è un caso banale)

PASSAGGIO 1) Rimuovere il collegamento interno tra i nodi collegati

PASSAGGIO 2) Collegare il nodo sul lato sinistro al nuovo nodo

PASSAGGIO 3) Collegare il nuovo nodo al nodo sul lato destro.

Operazione di cancellazione

Supponiamo un elenco collegato circolare a 3 nodi. I casi di cancellazione sono riportati di seguito:

  • Eliminazione dell'elemento corrente
  • Cancellazione dopo un elemento.

Cancellazione all'inizio / alla fine:

  1. Attraversa il primo nodo dall'ultimo nodo.
  2. Per eliminare dalla fine, dovrebbe esserci un solo passaggio di attraversamento, dall'ultimo nodo al primo nodo.
  3. Elimina il collegamento tra l'ultimo nodo e il nodo successivo.
  4. Collega l'ultimo nodo all'elemento successivo del primo nodo.
  5. Libera il primo nodo.

(Configurazione esistente)

FASE 1 ) Rimuovere il collegamento circolare

PASSI 2) Rimuovere il collegamento tra il primo e il successivo, collegare l'ultimo nodo, al nodo che segue il primo

FASE 3) Liberare / deallocare il primo nodo

Eliminazione dopo un nodo:

  1. Attraversa fino a quando il nodo successivo è il nodo da eliminare.
  2. Attraversa il nodo successivo, posizionando un puntatore sul nodo precedente.
  3. Collega il nodo precedente al nodo dopo il nodo attuale, usando il suo puntatore successivo.
  4. Liberare il nodo corrente (scollegato).

PASSAGGIO 1) Supponiamo di dover eliminare un nodo con "VALUE1".

PASSAGGIO 2) Rimuovere il collegamento tra il nodo precedente e il nodo corrente. Collega il suo nodo precedente con il nodo successivo puntato dal nodo corrente (con VALUE1).

FASE 3) Liberare o deallocare il nodo corrente.

Attraversamento di un elenco collegato circolare

Per attraversare un elenco collegato circolare, a partire da un ultimo puntatore, controllare se l'ultimo puntatore stesso è NULL. Se questa condizione è falsa, controlla se è presente un solo elemento. Altrimenti, attraversa usando un puntatore temporaneo fino a raggiungere di nuovo l'ultimo puntatore, o tutte le volte necessarie, come mostrato nella GIF qui sotto.

Vantaggi dell'elenco collegato circolare

Alcuni dei vantaggi degli elenchi concatenati circolari sono:

  1. Nessun requisito per un'assegnazione NULL nel codice. L'elenco circolare non punta mai a un puntatore NULL a meno che non venga completamente deallocato.
  2. Gli elenchi concatenati circolari sono vantaggiosi per le operazioni finali poiché l'inizio e la fine coincidono. Algoritmi come la pianificazione Round Robin possono eliminare ordinatamente i processi accodati in modo circolare senza incontrare puntatori penzolanti o referenziali NULL.
  3. L'elenco collegato circolare svolge anche tutte le normali funzioni di un elenco collegato singolarmente. In effetti, gli elenchi circolari a doppio collegamento discussi di seguito possono persino eliminare la necessità di un attraversamento a tutta lunghezza per individuare un elemento. Quell'elemento sarebbe al massimo esattamente opposto all'inizio, completando solo metà dell'elenco collegato.

Elenco collegato singolarmente come elenco collegato circolare

Sei incoraggiato a tentare di leggere e implementare il codice seguente. Presenta l'aritmetica dei puntatori associata agli elenchi concatenati circolari.

#include#includestruct node{int item;struct node *next;};struct node* addToEmpty(struct node*,int);struct node *insertCurrent(struct node *, int);struct node *insertAfter(struct node *, int, int);struct node *removeAfter(struct node *, int);struct node *removeCurrent(struct node *);void peek(struct node *);int main(){…

Spiegazione del codice:

  1. Le prime due righe di codice sono i file di intestazione inclusi necessari.
  2. La sezione successiva descrive la struttura di ogni nodo autoreferenziale. Contiene un valore e un puntatore dello stesso tipo della struttura.
  3. Ogni struttura si collega ripetutamente a oggetti struttura dello stesso tipo.
  4. Esistono diversi prototipi di funzioni per:
    1. Aggiunta di un elemento a un elenco collegato vuoto
    2. Inserimento nella posizione correntemente puntata di un elenco collegato circolare.
    3. Inserimento dopo un particolare valore indicizzato nell'elenco collegato.
    4. Rimozione / eliminazione dopo un particolare valore indicizzato nell'elenco collegato.
    5. Rimozione nella posizione attualmente indicata di un elenco collegato circolare
  5. L'ultima funzione stampa ogni elemento attraverso un attraversamento circolare in qualsiasi stato della lista collegata.
int main(){struct node *last = NULL;last = insertCurrent(last,4);last = removeAfter(last, 4);peek(last);return 0;}struct node* addToEmpty(struct node*last, int data){struct node *temp = (struct node *)malloc(sizeof( struct node));temp->item = data;last = temp;last->next = last;return last;}struct node *insertCurrent(struct node *last, int data)

Spiegazione del codice:

  1. Per il codice addEmpty, allocare un nodo vuoto utilizzando la funzione malloc.
  2. Per questo nodo, collocare i dati nella variabile temporanea.
  3. Assegna e collega l'unica variabile alla variabile temporanea
  4. Restituisce l'ultimo elemento al contesto main () / applicazione.
struct node *insertCurrent(struct node *last, int data){if(last == NULL){return addToEmpty(last, data);}struct node *temp = (struct node *)malloc(sizeof( struct node));temp -> item = data;temp->next = last->next;last->next = temp;return last;}struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;…

Spiegazione del codice

  1. Se non ci sono elementi da inserire, assicurati di aggiungere a un elenco vuoto e restituire il controllo.
  2. Crea un elemento temporaneo da posizionare dopo l'elemento corrente.
  3. Collega i puntatori come mostrato.
  4. Restituisce l'ultimo puntatore come nella funzione precedente.
… struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;if (last == NULL){return addToEmpty(last, item);}do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found. Please try again");…

Spiegazione del codice:

  1. Se non ci sono elementi nell'elenco, ignora i dati, aggiungi l'elemento corrente come ultimo elemento nell'elenco e restituisci il controllo
  2. Per ogni iterazione nel ciclo do-while assicurati che ci sia un puntatore precedente che contenga l'ultimo risultato attraversato.
  3. Solo allora può verificarsi il successivo attraversamento.
  4. Se i dati vengono trovati, o temp torna all'ultimo puntatore, il do-while termina. La sezione successiva del codice decide cosa deve essere fatto con l'elemento.
… if(temp->item != data){printf("Element not found. Please try again");return last;}else{newnode = (struct node *)malloc(sizeof(struct node));newnode->item = item;prev->next = newnode;newnode->next = temp;}return last;}struct node *removeCurrent(struct node *last)…

Spiegazione del codice:

  1. Se l'intero elenco è stato attraversato, ma l'elemento non è stato trovato, visualizzare un messaggio "elemento non trovato" e quindi restituire il controllo al chiamante.
  2. Se è stato trovato un nodo e / o il nodo non è ancora l'ultimo nodo, creare un nuovo nodo.
  3. Collega il nodo precedente con il nuovo nodo. Collega il nodo corrente con temp (la variabile di attraversamento).
  4. Ciò garantisce che l'elemento venga posizionato dopo un particolare nodo nell'elenco collegato circolare. Torna al chiamante.
struct node *removeCurrent(struct node *last){if(last == NULL){printf("Element Not Found");return NULL;}struct node *temp = last->next;last->next = temp->next;free(temp);return last;}struct node *removeAfter(struct node *last, int data)

Spiegazione del codice

  1. Per rimuovere solo l'ultimo nodo (corrente), controlla se questo elenco è vuoto. Se lo è, nessun elemento può essere rimosso.
  2. La variabile temp attraversa solo un collegamento in avanti.
  3. Collega l'ultimo puntatore al puntatore dopo il primo.
  4. Libera il puntatore della temperatura. Dealloca l'ultimo puntatore non collegato.
struct node *removeAfter(struct node *last,int data){struct node *temp = NULL,*prev = NULL;if (last == NULL){printf("Linked list empty. Cannot remove any element\n");return NULL;}temp = last->next;prev = temp;do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found");…

Spiegazione del codice

  1. Come con la precedente funzione di rimozione, controlla se non ci sono elementi. Se questo è vero, nessun elemento può essere rimosso.
  2. Ai puntatori vengono assegnate posizioni specifiche per individuare l'elemento da eliminare.
  3. I puntatori avanzano, uno dietro l'altro. (prev dietro temp)
  4. Il processo continua finché non viene trovato un elemento o l'elemento successivo torna all'ultimo puntatore.
if(temp->item != data){printf("Element not found");return last;}else{prev->next = temp->next;free(temp);}return last;}void peek(struct node * last){struct node *temp = last;if (last == NULL){return;

Spiegazione del programma

  1. Se l'elemento trovato dopo aver attraversato l'intero elenco collegato, viene visualizzato un messaggio di errore che informa che l'elemento non è stato trovato.
  2. In caso contrario, l'elemento viene scollegato e liberato nei passaggi 3 e 4.
  3. Il puntatore precedente è collegato all'indirizzo indicato come "successivo" dall'elemento da eliminare (temp).
  4. Il puntatore temporaneo viene quindi deallocato e liberato.
… void peek(struct node * last){struct node *temp = last;if (last == NULL){return;}if(last -> next == last){printf("%d-", temp->item);}while (temp != last){printf("%d-", temp->item);temp = temp->next;}}

Spiegazione del codice

  1. Il peek o il traversal non è possibile se non sono necessari zero. L'utente deve allocare o inserire un nodo.
  2. Se è presente un solo nodo, non è necessario attraversare, il contenuto del nodo può essere stampato e il ciclo while non viene eseguito.
  3. Se è presente più di un nodo, il temp stampa tutto l'elemento fino all'ultimo elemento.
  4. Nel momento in cui viene raggiunto l'ultimo elemento, il ciclo termina e la funzione restituisce la chiamata alla funzione principale.

Applicazioni della lista collegata circolare

  • Implementazione della pianificazione round-robin nei processi di sistema e della pianificazione circolare nella grafica ad alta velocità.
  • Programmazione dei token ring nelle reti di computer.
  • Viene utilizzato nelle unità di visualizzazione come le bacheche dei negozi che richiedono un attraversamento continuo dei dati.