Lista circular vinculada: vantagens e desvantagens

O que é uma lista vinculada circular?

Uma lista circular encadeada é uma sequência de nós organizados de forma que cada nó possa ser relido.traccada “nó” é um elemento autorreferencial com ponteiros para um ou dois nós em sua vizinhança imediata.

Abaixo está uma representação de uma lista vinculada circular com 3 nós.

Aqui, você pode ver que cada nó é retraccapaz de se autoencadear. O exemplo mostrado acima é uma lista circular simplesmente encadeada.

Nota: A lista encadeada circular mais simples é um único nó cujo ponteiro para o próximo nó tracretorna a si mesmo, como mostrado abaixo.

Básico Operações em listas circulares encadeadas

As três operações básicas em uma lista circular encadeada são:

1. Inclusão
2. Exclusão e
3. Traversal

• Inserção é o processo de colocar um nó em uma posição especificada na lista vinculada circular.
• A exclusão é o processo de remoção de um nó existente da lista vinculada. O nó pode ser identificado pela ocorrência do seu valor ou pela sua posição.
• A travessia de uma lista circular encadeada é o processo de exibir todo o conteúdo da lista e, em seguida, retornar ao início.tracretornando ao nó de origem.

A próxima seção explica como funciona a inserção e os dois tipos de inserção possíveis em uma lista circular simplesmente encadeada.

Inclusão Operação

Primeiro, você cria um nó cujo ponteiro "próximo" aponta de volta para ele mesmo, como mostrado abaixo. Sem esse nó inicial, a primeira inserção se torna o primeiro nó da lista.

A seguir, existem duas possibilidades:

• Inserção na posição atual da lista circular encadeada. Isso corresponde à inserção no início ou no fim de uma lista encadeada simples comum — em uma lista circular encadeada, o início e o fim são o mesmo ponto.
• Inserção após um nó indexado. O nó deve ser identificado por um número de índice correspondente ao valor do seu elemento.

Para inserir um elemento no início ou no final de uma lista circular encadeada — ou seja, na posição onde o primeiro nó foi adicionado — siga os passos abaixo:

• Você terá que quebrar o auto-link existente para o nó existente
• O próximo ponteiro do novo nó será vinculado ao nó existente.
• O próximo ponteiro do último nó apontará para o nó inserido.

NOTA: O ponteiro que marca o início ou o fim do círculo pode ser reatribuído a qualquer nó. Uma travessia ainda retornará ao mesmo nó, como discutido posteriormente neste artigo.

As etapas em (a) i-iii são mostradas abaixo:

(Nó existente)

Passo 1) Quebre o link existente

Passo 2) Crie um link direto (do novo nó para um nó existente)

Passo 3) Crie um link de loop para o primeiro nó

A seguir, você tentará a inserção após um nó.

Por exemplo, insira “VALOR2” após o nó que contém “VALOR0”, assumindo que o ponto de partida seja o nó com “VALOR0”.

• Quebre a ligação entre o primeiro e o segundo nó e coloque o nó com “VALOR2” entre eles.
• O ponteiro "próximo" do primeiro nó aponta para o novo nó, e o ponteiro "próximo" do novo nó aponta para o que era anteriormente o segundo nó.
• O restante da configuração permanece inalterado. Todos os nós são retraccapazes de si mesmos.

NOTA: Como a disposição é cíclica, o procedimento para inserir um nó é idêntico, independentemente da posição escolhida. O ponteiro que fecha o ciclo se comporta como qualquer outro ponteiro na lista.

Isso é mostrado abaixo:

(Digamos que existem apenas dois nós. Este é um caso trivial)

Passo 1) Remova o link interno entre os nós conectados

Passo 2) Conecte o nó do lado esquerdo ao novo nó

Passo 3) Conecte o novo nó ao nó do lado direito.

eliminação Operação

Considere uma lista circular encadeada com 3 nós. Os dois casos de exclusão são:

• Excluindo o elemento atual
• Exclusão após um elemento.

Exclusão no início/fim:

1. Vá para o primeiro nó a partir do último nó.
2. A exclusão a partir do final requer apenas uma etapa de percurso, do último nó para o primeiro nó.
3. Elimine a ligação entre o último nó e o primeiro nó.
4. Vincule o último nó ao próximo elemento do primeiro nó.
5. Libere o primeiro nó.

(Configuração existente)

Passo 1) Remova o link circular

Passo 2) Remova o link entre o primeiro e o próximo, vincule o último nó ao nó seguinte ao primeiro

Passo 3) Libere/desaloque o primeiro nó.

Exclusão após um nó:

1. Percorra a área até encontrar o próximo nó, que deve ser excluído.
2. Vá para o próximo nó, colocando um ponteiro no nó anterior.
3. Conecte o nó anterior ao nó após o nó atual, usando seu próximo ponteiro.
4. Libere o nó atual (desvinculado).

Passo 1) Digamos que precisamos excluir um nó com “VALUE1”.

Passo 2) Remova a ligação entre o nó anterior e o nó atual e, em seguida, ligue o nó anterior diretamente ao nó apontado pelo ponteiro "próximo" do nó atual (o nó após VALUE1).

Passo 3) Liberte ou desaloque o nó atual.

Travessia de uma lista vinculada circular

Para percorrer uma lista circular encadeada a partir de um ponteiro para o último elemento, primeiro verifique se esse ponteiro é NULL. Se não for NULL, verifique se a lista contém apenas um elemento. Caso contrário, percorra a lista com um ponteiro temporário até alcançar novamente o último elemento, como mostrado na animação abaixo.

Vantagens da lista vinculada circular

Algumas das vantagens das listas vinculadas circulares são:

1. Nenhum requisito para uma atribuição NULL no código. A lista circular nunca aponta para um ponteiro NULL, a menos que seja totalmente desalocada.
2. Listas circulares encadeadas são vantajosas para operações de fim de lista porque o início e o fim coincidem. Algorithms Mecanismos como o de escalonamento round-robin podem percorrer os processos enfileirados de forma limpa, sem encontrar ponteiros pendentes ou nulos.
3. Uma lista circular ainda suporta todas as operações regulares de uma lista simplesmente encadeada. lista duplamente encadeada Pode até eliminar a necessidade de percorrer toda a lista para localizar um elemento — no pior caso, o alvo fica em frente ao ponteiro inicial, então, no máximo, metade da lista precisa ser percorrida.

Desvantagens da lista vinculada circular

As desvantagens de usar uma lista vinculada circular estão abaixo:

1. Listas circulares são mais complexas do que listas vinculadas individualmente.
2. RevInverter uma lista circular é mais complexo do que inverter uma lista simplesmente ou duplamente encadeada.
3. Se o término do loop não for tratado com cuidado, o código de percurso pode entrar em um loop infinito.
4. É mais difícil encontrar o final da lista e escrever condições de controle de loop corretas.
5. Inserir um elemento no início da lista exige percorrer toda a lista para chegar ao último nó (do ponto de vista da implementação).

Lista vinculada individualmente como uma lista vinculada circular

Recomenda-se que você leia e implemente o código C abaixo. Ele ilustra a aritmética de ponteiros associada a uma lista encadeada simples circular.

#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()
{
...

Explicação do código:

1. As duas primeiras linhas de código são os arquivos de cabeçalho incluídos necessários.
2. A próxima seção define a estrutura de cada nó autorreferencial. Ela contém um valor e um ponteiro do mesmo tipo que a estrutura.
3. Cada instância de estrutura se vincula a outros objetos de estrutura do mesmo tipo.
4. Existem diferentes protótipos de funções para:
   1. Adicionando um elemento a uma lista vinculada vazia
   2. Inserindo no atualmente apontado posição de uma lista vinculada circular.
   3. Inserindo após um determinado indexado valor na lista vinculada.
   4. Remover/Excluir após um determinado indexado valor na lista vinculada.
   5. Removendo na posição atualmente apontada de uma lista vinculada circular
5. A última função imprime cada elemento através de um percurso circular em qualquer estado da lista vinculada.

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)

Explicação do código:

1. Para o código addToEmpty, aloque um nó vazio usando a função malloc().
2. Coloque os dados recebidos no nó temporário.
3. Atribua o nó temporário ao último e defina seu ponteiro "próximo" para si mesmo, de modo que o nó único aponte de volta para si mesmo.
4. Retorna o último ponteiro para o contexto da função main() / aplicação.

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;
…

Explicação do código

1. Se a lista estiver vazia, passe o controle para addToEmpty() e retorne o controle.
2. Crie um nó temporário para ser posicionado após o nó atual.
3. Conecte os ponteiros conforme mostrado no diagrama acima.
4. Retorna o último ponteiro, correspondendo ao padrão usado na função anterior.

...
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");
...

Explicação do código:

1. Se a lista estiver vazia, ignore a chave de pesquisa, adicione o item atual como o único nó da lista e retorne o controle.
2. Em cada iteração do loop do-while, um ponteiro anterior armazena o último resultado percorrido.
3. Só então ocorre a próxima etapa de travessia.
4. O laço do-while termina quando os dados de destino são encontrados ou quando a variável `temp` atinge novamente o último ponteiro. O bloco de código seguinte decide o que fazer com o item localizado.

...
    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)
...

Explicação do código:

1. Se a lista inteira tiver sido percorrida, mas o item não for encontrado, exiba a mensagem "Elemento não encontrado" e retorne o controle para quem chamou a função.
2. Se o nó de destino for encontrado, aloque um novo nó para o valor a ser inserido.
3. de vidrio o nó anterior para o novo nó e vincule o ponteiro "próximo" do novo nó a temp (a variável de percurso).
4. Isso coloca o novo elemento imediatamente após o nó de destino na lista circular encadeada. O controle então retorna para quem chamou a função.

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)

Explicação do código

1. Para remover o último (atual) nó, primeiro verifique se a lista está vazia. Se estiver, nenhum elemento pode ser removido.
2. A variável de temperatura avança um elo.
3. Vincule o último ponteiro ao nó seguinte ao primeiro nó.
4. Libere o ponteiro temporário para desalocar o nó não vinculado.

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");
...

Explicação do código

1. Assim como na função de remoção anterior, primeiro verifique se a lista está vazia. Se estiver, nenhum elemento poderá ser removido.
2. Dois ponteiros são atribuídas posições específicas para localizar o elemento a ser excluído.
3. Os indicadores avançam um após o outro (temp. das trilhas anteriores).
4. A busca continua até que o elemento alvo seja encontrado ou o ponteiro seguinte alcance o último nó novamente.

    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;

Explicação do programa

1. Se toda a lista encadeada for percorrida sem encontrar o alvo, será exibida a mensagem "Elemento não encontrado".
2. Caso contrário, o elemento é desvinculado e liberado nas etapas 3 e 4.
3. O ponteiro anterior está vinculado ao nó apontado pelo ponteiro seguinte de temp (o nó seguinte ao que está sendo excluído).
4. O ponteiro temporário é então liberado.

...
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;
    }
}

Explicação do código

1. A travessia por inspeção não é possível se não houver nós — o usuário deve primeiro alocar ou inserir um nó.
2. Se houver apenas um nó, nenhuma travessia é necessária — o conteúdo do nó é impresso diretamente e o loop while não é executado.
3. Se houver mais de um nó, a função `temp` imprime cada item até o último elemento.
4. No momento em que o último elemento é alcançado, o loop termina e a função retorna o controle para main().

Aplicações da Lista Circular Vinculada

• Implementação de agendamento round-robin em processos do sistema e agendamento circular em gráficos de alta velocidade.
• Agendamento de token ring em redes de computadores.
• Utilizado em unidades de exibição, como painéis digitais de lojas, que exigem a navegação contínua de dados.

Perguntas Frequentes