Lista vinculada circular: vantagens com exemplo de programa C

Índice:

Anonim

O que é uma lista vinculada circular?

Uma lista ligada circular é uma sequência de nós organizados de forma que cada nó possa ser reconstituído até si mesmo. Aqui, um "nó" é um elemento autorreferencial com ponteiros para um ou dois nós na vizinhança imediata de iI.

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

Aqui, você pode ver que cada nó é rastreável a si mesmo. O exemplo mostrado acima é uma lista circular ligada individualmente.

Nota: A lista ligada circular mais simples, é um nó que traça apenas a si mesmo, conforme mostrado

Neste tutorial de lista ligada circular, você aprenderá:

  • O que é uma lista vinculada circular?
  • Operações básicas
  • Operação de Inserção
  • Operação de Exclusão
  • Traversal de uma lista ligada circular
  • Vantagens da lista vinculada circular
  • Lista vinculada individualmente como uma lista vinculada circular
  • Aplicações da Lista Vinculada Circular

Operações básicas

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

  1. Inserção
  2. Exclusão e
  3. Travessia
  • A inserção é o processo de colocar um nó em uma posição especificada na lista ligada circular.
  • A exclusão é o processo de remoção de um nó existente da lista vinculada. O nó pode ser identificado pela ocorrência de seu valor ou por sua posição.
  • Traversal de uma lista ligada circular é o processo de exibir todo o conteúdo da lista ligada e retroceder de volta 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 Ligada Simplesmente.

Operação de Inserção

Inicialmente, você precisa criar um nó que aponta 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 ligada circular. Isso corresponde à inserção no início do final de uma lista vinculada singular regular. Em uma lista ligada 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 ligada 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 master ou o início / fim do círculo pode ser alterado. Ele ainda retornará ao mesmo nó em uma travessia, discutida adiante.

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

(Nó existente)

PASSO 1) Rompa o link existente

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

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

Em seguida, 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 ser vinculado a este nó, e o próximo ponteiro deste nó deve ser vinculado ao segundo nó anterior.
  • O resto do arranjo permanece inalterado. Todos os nós são retratáveis ​​para eles mesmos.

NOTA: Como existe um arranjo cíclico, inserir 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 haja apenas dois nós. Este é um caso trivial)

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

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

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

Operação de Exclusão

Vamos supor uma lista ligada 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á até 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, ligue o último nó, ao nó seguinte ao primeiro

ETAPA 3) Liberte / desaloque o primeiro nó

Exclusão após um nó:

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

ETAPA 1) Digamos que precisamos excluir um nó com "VALUE1".

ETAPA 2) Remova o link entre o nó anterior e o nó atual. Vincule seu nó anterior com o próximo nó apontado pelo nó atual (com VALUE1).

PASSO 3) Liberte ou desaloque o nó atual.

Traversal de uma lista ligada circular

Para percorrer uma lista ligada circular, começando de um último ponteiro, verifique se o último ponteiro é NULL. Se esta condição for falsa, verifique se existe apenas um elemento. Caso contrário, atravesse 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 circulares vinculadas 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 totalmente desalocada.
  2. Listas circulares ligadas são vantajosas para operações finais, uma vez que o início e o fim coincidem. Algoritmos como o escalonamento Round Robin podem eliminar nitidamente processos que são enfileirados de forma circular sem encontrar ponteiros oscilantes ou referenciais NULL.
  3. A lista ligada circular também executa todas as funções regulares de uma lista ligada individualmente. Na verdade, as listas circulares duplamente vinculadas discutidas abaixo podem até mesmo eliminar a necessidade de uma travessia de comprimento total para localizar um elemento. Esse elemento seria, no máximo, exatamente o oposto do início, completando apenas metade da lista vinculada.

Lista vinculada individualmente como uma lista vinculada circular

Recomendamos que você tente ler e implementar o código a seguir. Apresenta a aritmética de ponteiro associada a listas circulares vinculadas.

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

Explicação do código:

  1. As primeiras duas 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 se vincula repetidamente a objetos de estrutura do mesmo tipo.
  4. Existem diferentes protótipos de função para:
    1. Adicionando um elemento a uma lista vinculada vazia
    2. Inserindo na posição apontada atualmente de uma lista ligada circular.
    3. Inserindo após um determinado valor indexado na lista vinculada.
    4. Removendo / Excluindo após um determinado valor indexado na lista vinculada.
    5. Removendo na posição atualmente apontada de uma lista circular ligada
  5. A última função imprime cada elemento por meio de uma travessia 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 principal () / do 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. Retorna 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 contém o último resultado percorrido.
  3. Só então a próxima travessia pode ocorrer.
  4. Se os dados forem encontrados, ou se temp 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 foi percorrida, mas o item não foi encontrado, exiba uma mensagem "item não encontrado" e retorne o controle ao chamador.
  2. Se houver um nó encontrado e / ou o nó ainda não for o último nó, crie um novo nó.
  3. Vincule o nó anterior ao 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 ligada circular. Volte para o 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 pode ser removido.
  2. A variável temp apenas avança um link.
  3. Vincule o último ponteiro ao ponteiro após o primeiro.
  4. Libere o ponteiro temporário. 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. Como na função de remoção anterior, verifique se não há nenhum elemento. Se isso for verdade, nenhum elemento pode ser removido.
  2. Ponteiros são atribuídos a posições específicas para localizar o elemento a ser excluído.
  3. Os indicadores 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 retroceda até o ú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 é 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 não houver necessidade de zero. O usuário precisa alocar ou inserir um nó.
  2. Se houver apenas um nó, não há necessidade de atravessar, o conteúdo do nó pode ser impresso e o loop while não é executado.
  3. Se houver mais de um nó, o temporário imprime todos os itens 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 Vinculada Circular

  • Implementação de escalonamento round-robin em processos do sistema e escalonamento circular em gráficos de alta velocidade.
  • Programação de token ring em redes informáticas.
  • Ele é usado em unidades de exibição, como placas de loja, que exigem uma passagem contínua de dados.