Lista circular vinculada: vantagens e desvantagens

O que é uma lista vinculada circular?

Uma lista vinculada circular é uma sequência de nós organizados de forma que cada nó possa ser rastreado até si mesmo. Aqui, um “nó” é um elemento auto-referencial com ponteiros para um ou dois nós nas suas imediações.

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

Aqui, você pode ver que cada nó pode ser rastreado até si mesmo. O exemplo mostrado acima é uma lista circular vinculada individualmente.

Nota: A lista vinculada circular mais simples é um nó que rastreia apenas a si mesmo, conforme mostrado

Basico Operações em listas circulares vinculadas

As operações básicas em uma lista vinculada circular 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 vinculada circular é o processo de exibir todo o conteúdo da lista vinculada e retornar ao nó de origem.

Na próxima seção, você entenderá a inserção de um nó e os tipos de inserção possíveis em uma lista circular simples vinculada.

Inclusão Operação

Inicialmente, você precisa criar um nó que aponte para si mesmo, conforme mostrado nesta imagem. Sem este nó, a inserção cria o primeiro nó.

A seguir, existem duas possibilidades:

• Inserção na posição atual da lista vinculada circular. Isso corresponde à inserção no início do final de uma lista vinculada singular regular. Em uma lista vinculada circular, o início e o fim são iguais.
• 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 no início/fim da lista vinculada circular, ou seja, na posição onde o primeiro nó foi adicionado,

• 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 é o token mestre ou o início/fim do círculo pode ser alterado. Ele ainda retornará ao mesmo nó em uma travessia, discutida a seguir.

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, vamos inserir “VALUE2” após o nó com “VALUE0”. Suponhamos que o ponto de partida seja o nó com “VALUE0”.

• Você terá que quebrar a linha entre o primeiro e o segundo nó e colocar o nó com “VALUE2” no meio.
• O próximo ponteiro do primeiro nó deve vincular-se a este nó, e o próximo ponteiro deste nó deve vincular-se ao segundo nó anterior.
• O resto do acordo permanece inalterado. Todos os nós são rastreáveis ​​até si mesmos.

NOTA: Como existe um arranjo cíclico, a inserção de um nó envolve o mesmo procedimento para qualquer nó. O ponteiro que completa um ciclo completa o ciclo como qualquer outro nó.

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

Vamos supor uma lista vinculada circular de 3 nós. Os casos de exclusão são fornecidos abaixo:

• 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. Para excluir do final, deve haver apenas uma etapa de travessia, do último nó ao primeiro nó.
3. Exclua o link entre o último nó e o próximo 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

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

PASSO 3) Liberar/deallocar o primeiro nó

Exclusão após um nó:

1. Percorra até o próximo nó ser o nó a 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 o link entre o nó anterior e o nó atual. Vincule seu nó anterior ao próximo nó apontado pelo nó atual (com VALUE1).

PASSO 3) Liberte ou desaloque o nó atual.

Travessia de uma lista vinculada circular

Para percorrer uma lista vinculada circular, começando pelo último ponteiro, verifique se o último ponteiro é NULL. Se esta condição for falsa, verifique se existe apenas um elemento. Caso contrário, percorra usando um ponteiro temporário até que o último ponteiro seja alcançado novamente, ou quantas vezes forem necessárias, conforme mostrado no GIF 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 vinculadas circulares são vantajosas para operações finais, pois o início e o fim coincidem. Algorithms como o agendamento Round Robin pode eliminar perfeitamente processos que são enfileirados de maneira circular, sem encontrar ponteiros pendentes ou referenciais NULL.
3. A lista vinculada circular também executa todas as funções regulares de uma lista vinculada individualmente. Na verdade, circular listas duplamente vinculadas discutido abaixo pode até eliminar a necessidade de um percurso completo para localizar um elemento. Esse elemento seria, no máximo, exatamente oposto ao início, completando apenas metade da lista vinculada.

Desvantagens da lista vinculada circular

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

1. As listas circulares são complexas em comparação com listas vinculadas individualmente.
2. RevO oposto da lista circular é complexo quando comparado às listas simples ou duplas.
3. Se não for tratado com cuidado, o código poderá entrar em um loop infinito.
4. Mais difícil encontrar o final da lista e o controle do loop.
5. Inserindo no início, temos que percorrer a lista completa para encontrar o último nó. (Perspectiva de Implementação)

Lista vinculada individualmente como uma lista vinculada circular

Você é incentivado a tentar ler e implementar o código abaixo. Apresenta a aritmética de ponteiros associada a listas vinculadas circulares.

#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 descreve a estrutura de cada nó autorreferencial. Ele contém um valor e um ponteiro do mesmo tipo da estrutura.
3. Cada estrutura é vinculada repetidamente a 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 addEmpty, aloque um nó vazio usando a função malloc.
2. Para este nó, coloque os dados na variável temporária.
3. Atribua e vincule a única variável à variável temporária
4. Retorne o último elemento ao contexto main()/aplicativo.

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 não houver nenhum elemento para inserir, certifique-se de adicionar a uma lista vazia e retornar o controle.
2. Crie um elemento temporário para colocar após o elemento atual.
3. Vincule os ponteiros conforme mostrado.
4. Retorne o último ponteiro como 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 não houver nenhum elemento na lista, ignore os dados, adicione o item atual como o último item da lista e retorne o controle
2. Para cada iteração no loop do-while, certifique-se de que haja um ponteiro anterior que contenha o último resultado percorrido.
3. Só então a próxima travessia poderá ocorrer.
4. Se os dados forem encontrados ou a temperatura voltar ao último ponteiro, o do-while termina. A próxima seção do código decide o que deve ser feito com o item.

...
    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 toda a lista tiver sido percorrida, mas o item não for encontrado, exiba uma mensagem “item não encontrado” e devolva o controle ao chamador.
2. Se um nó for encontrado e/ou o nó ainda não for o último nó, crie um novo nó.
3. Ligação o nó anterior com o novo nó. Vincule o nó atual com temp (a variável de passagem).
4. Isso garante que o elemento seja colocado após um nó específico na lista vinculada circular. Retorne ao chamador.

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 apenas o último nó (atual), verifique se esta lista está vazia. Se for, nenhum elemento poderá ser removido.
2. A variável temp apenas atravessa um link adiante.
3. Vincule o último ponteiro ao ponteiro após o primeiro.
4. Libere o ponteiro de temperatura. Ele desaloca o último ponteiro 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. Tal como acontece com a função de remoção anterior, verifique se não há nenhum elemento. Se isso for verdade, nenhum elemento poderá ser removido.
2. Ponteiros são atribuídas posições específicas para localizar o elemento a ser excluído.
3. Os ponteiros são avançados, um atrás do outro. (anterior atrás da temperatura)
4. O processo continua até que um elemento seja encontrado ou o próximo elemento retorne ao último ponteiro.

    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 o elemento for encontrado após percorrer toda a lista vinculada, uma mensagem de erro será exibida informando que o item não foi encontrado.
2. Caso contrário, o elemento será desvinculado e liberado nas etapas 3 e 4.
3. O ponteiro anterior está vinculado ao endereço apontado como “próximo” pelo elemento a ser excluído (temp).
4. O ponteiro temporário é, portanto, desalocado e 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 espiada ou travessia não é possível se houver necessidade de zero. O usuário precisa alocar ou inserir um nó.
2. Se houver apenas um nó, não há necessidade de percorrer, o conteúdo do nó pode ser impresso e o loop while não é executado.
3. Se houver mais de um nó, o temp imprimirá todo o item até o último elemento.
4. No momento em que o último elemento é alcançado, o loop termina e a função retorna a chamada para a função principal.

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.
• Escalonamento de Token Rings em redes de computadores.
• Ele é usado em unidades de exibição, como painéis de lojas, que exigem passagem contínua de dados.