Lista collegata circolare: vantaggi e svantaggi

Che cos'è una lista collegata circolare?

Una lista concatenata circolare è una sequenza di nodi disposti in modo che ogni nodo possa essere ritrace a se stesso. Ogni “nodo” è un elemento autoreferenziale con puntatori a uno o due nodi nelle sue immediate vicinanze.

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

Qui puoi vedere che ogni nodo è ritraccollegabile a se stesso. L'esempio mostrato sopra è una lista circolare concatenata singolarmente.

Nota: la lista concatenata circolare più semplice è un singolo nodo il cui puntatore successivo tractorna a se stesso, come mostrato di seguito.

Basic Operazioni nelle liste concatenate circolari

Le tre operazioni di base su una lista concatenata circolare sono:

1. Inserimento
2. Cancellazione e
3. Traversal

• L'inserimento è il processo di posizionamento di un nodo in una posizione specifica 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 una lista concatenata circolare è il processo di visualizzazione dell'intero contenuto della lista concatenata e di ritractornando al nodo sorgente.

La sezione successiva spiega come funziona l'inserimento e i due tipi di inserimento possibili in una lista circolare concatenata singolarmente.

Inserimento Operaproduzione

Per prima cosa, si crea un nodo il cui puntatore "next" punti a se stesso, come mostrato di seguito. Senza questo nodo iniziale, il primo inserimento diventa il primo nodo della lista.

Successivamente ci sono due possibilità:

• Inserimento nella posizione corrente della lista concatenata circolare. Ciò corrisponde all'inserimento all'inizio o alla fine di una normale lista concatenata singola; in una lista concatenata circolare, l'inizio e la fine coincidono.
• Inserimento dopo un nodo indicizzato. Il nodo dovrebbe essere identificato da un numero di indice corrispondente al valore del suo elemento.

Per inserire un nodo all'inizio o alla fine della lista concatenata circolare, ovvero nella posizione in cui è stato aggiunto il primo nodo, segui i passaggi seguenti:

• Dovrai interrompere il collegamento automatico esistente al nodo esistente
• Il puntatore successivo del nuovo nodo si collegherà al nodo esistente.
• Il puntatore successivo dell'ultimo nodo punterà al nodo inserito.

NOTA: Il puntatore che indica l'inizio o la fine del cerchio può essere riassegnato a qualsiasi nodo. L'attraversamento ritornerà comunque allo stesso nodo, come spiegato più avanti in questo articolo.

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

(Nodo esistente)

Passo 1) Interrompi il collegamento esistente

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

Passo 3) Crea un collegamento ad anello al primo nodo

Successivamente, proverai l'inserimento dopo un nodo.

Ad esempio, inserire “VALORE2” dopo il nodo che contiene “VALORE0”, supponendo che il punto di partenza sia il nodo con “VALORE0”.

• Interrompi il collegamento tra il primo e il secondo nodo e posiziona il nodo con "VALUE2" nel mezzo.
• Il puntatore "next" del primo nodo punta al nuovo nodo, e il puntatore "next" del nuovo nodo punta a quello che in precedenza era il secondo nodo.
• Il resto della disposizione rimane invariato. Tutti i nodi sono ritracin grado di badare a se stessi.

NOTA: Poiché la disposizione è ciclica, la procedura per inserire un nodo è identica indipendentemente dalla posizione scelta. Il puntatore che chiude il ciclo si comporta come qualsiasi altro puntatore nell'elenco.

Questo è mostrato di seguito:

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

Passo 1) Rimuovere il collegamento interno tra i nodi collegati

Passo 2) Collega il nodo sul lato sinistro al nuovo nodo

Passo 3) Collega il nuovo nodo al nodo sul lato destro.

cancellazione Operaproduzione

Si consideri una lista concatenata circolare a 3 nodi. I due casi di cancellazione sono:

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

Cancellazione all'inizio/alla fine:

1. Attraversa al primo nodo dall'ultimo nodo.
2. L'eliminazione dalla fine richiede un solo passaggio di attraversamento, dall'ultimo nodo al primo nodo.
3. Elimina il collegamento tra l'ultimo nodo e il primo nodo.
4. Collega l'ultimo nodo all'elemento successivo del primo nodo.
5. Liberare il primo nodo.

(Configurazione esistente)

Passo 1) Rimuovere il collegamento circolare

Passo 2) Rimuovi il collegamento tra il primo e il successivo, collega l'ultimo nodo al nodo successivo al primo

Passo 3) Liberare/deallocare il primo nodo

Cancellazione dopo un nodo:

1. Proseguire lungo il percorso fino a quando il nodo successivo non è il nodo da eliminare.
2. Passare al nodo successivo, posizionando un puntatore sul nodo precedente.
3. Connetti il ​​nodo precedente al nodo successivo al nodo presente, utilizzando il suo puntatore successivo.
4. Liberare il nodo corrente (non collegato).

Passo 1) Diciamo che dobbiamo eliminare un nodo con "VALUE1".

Passo 2) Rimuovi il collegamento tra il nodo precedente e il nodo corrente, quindi collega il nodo precedente direttamente al nodo indicato dal puntatore next del nodo corrente (il nodo successivo a VALUE1).

Passo 3) Liberare o deallocare il nodo corrente.

Attraversamento di una lista concatenata circolare

Per attraversare una lista concatenata circolare a partire da un puntatore finale, si verifica innanzitutto se il puntatore finale è NULL. Se non è NULL, si controlla se la lista contiene un solo elemento. Altrimenti, si percorre la lista con un puntatore temporaneo fino a raggiungere nuovamente il puntatore finale, come mostrato nell'animazione sottostante.

Vantaggi della lista collegata circolare

Alcuni dei vantaggi degli elenchi collegati 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 sia completamente deallocato.
2. Le liste concatenate circolari sono vantaggiose per le operazioni di fine lista perché l'inizio e la fine coincidono. Algorithms come ad esempio la pianificazione round-robin può scorrere i processi in coda in modo pulito, senza incontrare puntatori pendenti o NULL.
3. Una lista concatenata circolare supporta ancora tutte le normali operazioni di una lista concatenata singola. Una lista circolare lista doppiamente collegata Può persino eliminare la necessità di una traversata completa per individuare un elemento: nel peggiore dei casi, l'elemento di destinazione si trova di fronte al puntatore di partenza, quindi al massimo è necessario percorrere metà della lista.

Svantaggi della lista collegata circolare

Gli svantaggi nell'utilizzo di un elenco collegato circolare sono i seguenti:

1. Gli elenchi circolari sono più complessi di elenchi collegati singolarmente.
2. RevInvertire una lista circolare è più complesso che invertire una lista concatenata singolarmente o doppiamente.
3. Se la terminazione del ciclo non viene gestita con attenzione, il codice di attraversamento può entrare in un ciclo infinito.
4. È più difficile trovare la fine dell'elenco e scrivere le condizioni di controllo del ciclo corrette.
5. L'inserimento all'inizio richiede di attraversare l'intera lista per raggiungere l'ultimo nodo (dal punto di vista implementativo).

Lista concatenata singolarmente come lista concatenata circolare

Si consiglia di leggere e implementare il codice C riportato di seguito. Esso illustra l'aritmetica dei puntatori associata a una lista concatenata singola circolare.

#include<stdio.h>
#include<stdlib.h>

struct 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 definisce la struttura di ciascun nodo autoreferenziale. Essa contiene un valore e un puntatore dello stesso tipo della struttura.
3. Ogni istanza di struttura si collega ad altri oggetti struttura dello stesso tipo.
4. Esistono diversi prototipi di funzioni per:
   1. Aggiunta di un elemento a un elenco collegato vuoto
   2. Inserimento al attualmente puntato posizione di un elenco circolare collegato.
   3. Inserimento dopo un particolare indicizzati valore nell'elenco collegato.
   4. Rimuovere/Cancellare dopo un particolare indicizzati valore nell'elenco collegato.
   5. Rimozione nella posizione attualmente puntata di un elenco collegato circolare
5. L'ultima funzione stampa ogni elemento attraverso un attraversamento circolare in qualsiasi stato della lista concatenata.

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 addToEmpty, alloca un nodo vuoto utilizzando la funzione malloc().
2. Inserisci i dati in arrivo nel nodo temporaneo.
3. Assegna il nodo temporaneo all'ultimo posto e imposta il suo puntatore "next" su se stesso, in modo che il singolo nodo punti nuovamente a se stesso.
4. Restituisce l'ultimo puntatore al contesto main() / dell'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 la lista è vuota, passa il controllo al metodo addToEmpty() e restituiscilo.
2. Crea un nodo temporaneo da posizionare dopo il nodo corrente.
3. Collega i puntatori come mostrato nel diagramma qui sopra.
4. Restituisce l'ultimo puntatore, corrispondente al modello utilizzato 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 l'elenco è vuoto, ignora il tasto di ricerca, aggiungi l'elemento corrente come unico nodo nell'elenco e restituisci il controllo.
2. In ogni iterazione del ciclo do-while, un puntatore "previous" contiene il risultato dell'ultima iterazione.
3. Solo allora si verifica la fase di attraversamento successiva.
4. Il ciclo do-while termina quando vengono trovati i dati di destinazione o quando temp raggiunge nuovamente l'ultimo puntatore. Il seguente blocco di codice decide cosa fare con l'elemento trovato.

...
    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 percorso ma l'elemento non è stato trovato, visualizza il messaggio "Elemento non trovato" e restituisci il controllo al chiamante.
2. Se il nodo di destinazione viene trovato, alloca un nuovo nodo per il valore da inserire.
3. vetro collega il puntatore del nodo precedente al nuovo nodo e collega il puntatore "next" del nuovo nodo a temp (la variabile di attraversamento).
4. Questo inserisce il nuovo elemento immediatamente dopo il nodo di destinazione nella lista concatenata circolare. Il controllo ritorna quindi 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 l'ultimo nodo (quello corrente), verifica innanzitutto se la lista è vuota. In tal caso, non è possibile rimuovere alcun elemento.
2. La variabile di temperatura fa avanzare un collegamento in avanti.
3. Collega l'ultimo puntatore al nodo successivo al primo nodo.
4. Libera il puntatore temporaneo per deallocare il nodo 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 per la precedente funzione di rimozione, si verifica innanzitutto se l'elenco è vuoto. In tal caso, non è possibile rimuovere alcun elemento.
2. Due puntatori vengono assegnate posizioni specifiche per individuare l'elemento da eliminare.
3. Gli indicatori avanzano uno dietro l'altro (temp. tracce precedenti).
4. L'attraversamento continua finché non viene trovato l'elemento di destinazione o finché il puntatore successivo non raggiunge nuovamente l'ultimo nodo.

    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 si percorre l'intera lista concatenata senza trovare l'elemento desiderato, viene visualizzato il messaggio "Elemento non trovato".
2. Altrimenti, l'elemento viene scollegato e liberato nei passaggi 3 e 4.
3. Il puntatore precedente è collegato al nodo puntato dal puntatore successivo di temp (il nodo successivo a quello che viene eliminato).
4. Il puntatore della temperatura viene quindi 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. L'attraversamento peek non è possibile se non sono presenti nodi: l'utente deve prima allocare o inserire un nodo.
2. Se è presente un solo nodo, non è necessario alcun attraversamento: il contenuto del nodo viene stampato direttamente e il ciclo while non viene eseguito.
3. Se è presente più di un nodo, temp stampa ogni elemento fino all'ultimo.
4. Nel momento in cui viene raggiunto l'ultimo elemento, il ciclo termina e la funzione restituisce il controllo a main().

Applicazioni della Lista Circolare Collegata

• Implementazione della pianificazione round-robin nei processi di sistema e della pianificazione circolare nella grafica ad alta velocità.
• Pianificazione ad anello token nelle reti di computer.
• Utilizzato in dispositivi di visualizzazione come i pannelli digitali dei negozi che richiedono un flusso continuo di dati.

DOMANDE FREQUENTI