Lista collegata circolare: vantaggi e svantaggi

Che cos'è una lista collegata circolare?

Una lista concatenata 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 sue immediate vicinanze.

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

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

Nota: l'elenco collegato circolare più semplice è un nodo che traccia solo se stesso come mostrato

Basic Operazioni nelle liste circolari collegate

Le 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 un elenco collegato circolare è il processo di visualizzazione del contenuto dell'intero elenco collegato e di ritorno al nodo di origine.

Nel paragrafo successivo si capirà l'inserimento di un nodo, e le tipologie di inserimento possibili in una Lista Circolare Singly Linked.

Inserimento Operaproduzione

Inizialmente, devi 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 circolare collegata. 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/fine della lista concatenata circolare, cioè nella posizione in cui è stato aggiunto il primo nodo in assoluto,

• 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: è possibile modificare il puntatore che costituisce il token master o l'inizio/fine del cerchio. Tornerà comunque allo stesso nodo durante una traversata, discussa in seguito.

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, 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 riconducibili 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)

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

Supponiamo una lista concatenata circolare a 3 nodi. Di seguito i casi di cancellazione:

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

Cancellazione all'inizio/alla fine:

1. Attraversa al primo nodo dall'ultimo nodo.
2. Per eliminare dalla fine, dovrebbe esserci un solo passaggio trasversale, 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. Liberare il primo nodo.

(Configurazione esistente)

STEP 1) Rimuovere il collegamento circolare

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

PASSO 3) Libera/dealloca il primo nodo

Cancellazione dopo un nodo:

1. Attraversa fino a quando il nodo successivo è 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) 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).

PASSO 3) Liberare o deallocare il nodo corrente.

Attraversamento di una lista concatenata circolare

Per attraversare una lista concatenata circolare, partendo da un ultimo puntatore, controlla se l'ultimo puntatore stesso è NULL. Se questa condizione è falsa, controlla se c'è un solo elemento. Altrimenti, attraversa usando un puntatore temporaneo finché non viene raggiunto di nuovo l'ultimo puntatore, o tutte le volte che servono, come mostrato nella GIF qui sotto.

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 finali poiché inizio e fine coincidono. Algorithms come la pianificazione Round Robin può eliminare nettamente i processi che sono accodati in modo circolare senza incontrare puntatori pendenti o referenziali NULL.
3. L'elenco concatenato circolare esegue anche tutte le normali funzioni di un elenco concatenato singolo. In effetti, circolare elenchi doppiamente collegati discusso di seguito può persino eliminare la necessità di un attraversamento completo per individuare un elemento. Al massimo quell'elemento sarebbe esattamente opposto all'inizio, completando solo la metà dell'elenco concatenato.

Svantaggi della lista collegata circolare

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

1. Gli elenchi circolari sono complessi rispetto a elenchi collegati singolarmente.
2. RevLa serie di elenchi circolari è più complessa rispetto agli elenchi singoli o doppi.
3. Se non gestito con attenzione, il codice potrebbe eseguire un ciclo infinito.
4. È più difficile trovare la fine dell'elenco e il controllo del loop.
5. Inserendo in Start, dobbiamo percorrere l'elenco completo per trovare l'ultimo nodo. (Prospettiva di implementazione)

Lista concatenata singolarmente come lista concatenata circolare

Ti invitiamo a provare a leggere e implementare il codice seguente. Presenta l'aritmetica dei puntatori associata alle liste circolari concatenate.

#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 descrive la struttura di ciascun 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 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 addEmpty, allocare un nodo vuoto utilizzando la funzione malloc.
2. Per questo nodo, inserisci 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 aggiungerli 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 è presente alcun elemento nell'elenco, ignora i dati, aggiunge l'elemento corrente come ultimo elemento nell'elenco e restituisce il controllo
2. Per ogni iterazione nel ciclo do- while assicurarsi che sia presente un puntatore precedente che contenga l'ultimo risultato attraversato.
3. Solo allora potrà avvenire la traversata successiva.
4. Se i dati vengono trovati o se temp ritorna 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 è stato esplorato l'intero elenco, ma l'elemento non viene trovato, viene visualizzato il 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, crea un nuovo nodo.
3. Link il nodo precedente con il nuovo nodo. Collega il nodo corrente con temp (la variabile trasversale).
4. Ciò garantisce che l'elemento venga posizionato dopo un nodo particolare nell'elenco collegato circolare. Ritorna 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 semplicemente un collegamento in avanti.
3. Collega l'ultimo puntatore al puntatore dopo il primo.
4. Liberare il puntatore temporaneo. Disalloca 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 c'è alcun elemento. Se questo è vero, allora nessun elemento può essere rimosso.
2. Puntatori vengono assegnate posizioni specifiche per individuare l'elemento da eliminare.
3. I puntatori vengono avanzati, uno dietro l'altro. (precedente dietro la temperatura)
4. Il processo continua finché non viene trovato un elemento o l'elemento successivo ritorna 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 viene 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 è legato 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. La sbirciatina o l'attraversamento non sono possibili se non sono necessari zero. L'utente deve allocare o inserire un nodo.
2. Se è presente un solo nodo, non è necessario attraversarlo, il contenuto del nodo può essere stampato e il ciclo while non viene eseguito.
3. Se è presente più di un nodo, 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 Circolare Collegata

• 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 in unità di visualizzazione come i tabelloni dei negozi che richiedono l'attraversamento continuo di dati.