circular linked list data structure c with illustration
Uma visão geral completa da lista vinculada circular.
Uma lista ligada circular é uma variação da lista ligada. É uma lista encadeada cujos nós estão conectados de tal forma que formam um círculo.
Na lista ligada circular, o próximo ponteiro do último nó não é definido como nulo, mas contém o endereço do primeiro nó, formando assim um círculo.
=> Visite aqui para aprender C ++ do zero.
O que você aprenderá:
Lista vinculada circular em C ++
O arranjo mostrado abaixo é para uma lista unida individualmente.
Uma lista ligada circular pode ser uma lista ligada individualmente ou uma lista duplamente ligada. Em uma lista duplamente circular ligada, o ponteiro anterior do primeiro nó é conectado ao último nó, enquanto o próximo ponteiro do último nó é conectado ao primeiro nó.
Sua representação é mostrada a seguir.
Declaração
Podemos declarar um nó em uma lista ligada circular como qualquer outro nó, conforme mostrado abaixo:
struct Node { int data; struct Node *next; }; Para implementar a lista ligada circular, mantemos um ponteiro externo “last” que aponta para o último nó na lista ligada circular. Portanto, last-> next apontará para o primeiro nó na lista vinculada.
Fazendo isso, garantimos que, ao inserir um novo nó no início ou no final da lista, não precisamos percorrer a lista inteira. Isso ocorre porque o último aponta para o último nó enquanto last-> next aponta para o primeiro nó.
Isso não teria sido possível se tivéssemos apontado o ponteiro externo para o primeiro nó.
Operações básicas
A lista ligada circular oferece suporte para inserção, exclusão e passagem da lista. Discutiremos cada uma das operações em detalhes agora.
Inserção
Podemos inserir um nó em uma lista ligada circular como um primeiro nó (lista vazia), no início, no final ou entre os outros nós. Vamos ver cada uma dessas operações de inserção usando uma representação pictórica abaixo.
# 1) Inserir em uma lista vazia
Quando não há nós na lista circular e a lista está vazia, o último ponteiro é nulo, então inserimos um novo nó N apontando o último ponteiro para o nó N como mostrado acima. O próximo ponteiro de N apontará para o próprio nó N, pois há apenas um nó. Assim, N se torna o primeiro e o último nó da lista.
# 2) Insira no início da lista
Conforme mostrado na representação acima, quando adicionamos um nó no início da lista, o próximo ponteiro do último nó aponta para o novo nó N, tornando-o assim um primeiro nó.
N-> próximo = último-> próximo
Último-> próximo = N
# 3) Insira no final da lista
Para inserir um novo nó no final da lista, seguimos estas etapas:
óculos de realidade virtual para xbox 360
N-> próximo = último -> próximo;
último -> próximo = N
último = N
# 4) Insira entre a lista
Suponha que precisemos inserir um novo nó N entre N3 e N4, primeiro precisamos percorrer a lista e localizar o nó após o qual o novo nó deve ser inserido, neste caso, seu N3.
Depois que o nó é localizado, executamos as seguintes etapas.
N -> próximo = N3 -> próximo;
N3 -> próximo = N
Isso insere um novo nó N após N3.
Eliminação
A operação de exclusão da lista ligada circular envolve localizar o nó que deve ser excluído e, em seguida, liberar sua memória.
Para isso, mantemos dois ponteiros adicionais curr e prev e então percorremos a lista para localizar o nó. O nó fornecido a ser excluído pode ser o primeiro nó, o último nó ou o nó intermediário. Dependendo da localização, definimos os ponteiros curr e prev e, em seguida, excluímos o nó curr.
Uma representação pictórica da operação de exclusão é mostrada abaixo.
Travessia
Traversal é uma técnica de visitar cada um dos nós. Em listas vinculadas lineares, como listas unidas individualmente e listas duplamente vinculadas, o percurso é fácil, pois visitamos cada nó e paramos quando NULL é encontrado.
No entanto, isso não é possível em uma lista ligada circular. Em uma lista ligada circular, partimos do próximo nó do último, que é o primeiro nó, e percorremos cada nó. Paramos quando mais uma vez alcançamos o primeiro nó.
Agora apresentamos uma implementação das operações de lista ligada circular usando C ++ e Java. Implementamos operações de inserção, exclusão e passagem aqui. Para uma compreensão clara, descrevemos a lista ligada circular como
Assim, ao último nó 50, anexamos novamente o nó 10, que é o primeiro nó, indicando-o como uma lista ligada circular.
#include using namespace std; struct Node { int data; struct Node *next; }; //insert a new node in an empty list struct Node *insertInEmpty(struct Node *last, int new_data) { // if last is not null then list is not empty, so return if (last != NULL) return last; // allocate memory for node struct Node *temp = new Node; // Assign the data. temp -> data = new_data; last = temp; // Create the link. last->next = last; return last; } //insert new node at the beginning of the list struct Node *insertAtBegin(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //set new data to node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; return last; } //insert new node at the end of the list struct Node *insertAtEnd(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //assign data to new node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; last = temp; return last; } //insert a new node in between the nodes struct Node *insertAfter(struct Node *last, int new_data, int after_item) { //return null if list is empty if (last == NULL) return NULL; struct Node *temp, *p; p = last -> next; do { if (p ->data == after_item) { temp = new Node; temp -> data = new_data; temp -> next = p -> next; p -> next = temp; if (p == last) last = temp; return last; } p = p -> next; } while(p != last -> next); cout << 'The node with data '< next; // Point to the first Node in the list. // Traverse the list starting from first node until first node is visited again do { cout < data <'; p = p -> next; } while(p != last->next); if(p == last->next) coutdata==key && (*head)->next==*head) { free(*head); *head=NULL; } Node *last=*head,*d; // If key is the head if((*head)->data==key) { while(last->next!=*head) // Find the last node of the list last=last->next; // point last node to next of head or second node of the list last->next=(*head)->next; free(*head); *head=last->next; } // end of list is reached or node to be deleted not there in the list while(last->next!=*head&&last->next->data!=key) { last=last->next; } // node to be deleted is found, so free the memory and display the list if(last->next->data==key) { d=last->next; last->next=d->next; cout<<'The node with data '< Resultado:
A lista circular ligada criada é a seguinte:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
O nó com dados 10 é excluído da lista
A lista ligada circular após a exclusão de 10 é a seguinte:
20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 20
A seguir, apresentamos uma implementação Java para as operações de lista vinculada Circular.
//Java class to demonstrate circular linked list operations class Main { static class Node { int data; Node next; }; //insert a new node in the empty list static Node insertInEmpty(Node last, int new_data) { // if list is not empty, return if (last != null) return last; Node temp = new Node(); // create a new node temp.data = new_data; // assign data to new node last = temp; last.next = last; // Create the link return last; } //insert a new node at the beginning of the list static Node insertAtBegin(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); //set data for the node temp.data = new_data; temp.next = last.next; last.next = temp; return last; } //insert a new node at the end of the list static Node insertAtEnd(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); temp.data = new_data; temp.next = last.next; last.next = temp; last = temp; return last; } //insert node in between the nodes in the list static Node addAfter(Node last, int new_data, int after_item) { //if list is null, return if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == after_item) { temp = new Node(); temp.data = new_data; temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; { while(p != last.next); System.out.println('The node with data ' + after_item + ' not present in the list.'); return last; } //traverse the circular linked list static void traverse(Node last) { Node p; // If list is empty, return. if (last == null) { System.out.println('Cicular linked List is empty.'); return; } p = last.next; // Point to first Node of the list. // Traversing the list. do{ System.out.print(p.data + '==>'); p = p.next; } while(p != last.next); if(p == last.next) System.out.print(p.data); System.out.print('
'); } //delete a node from the list static Node deleteNode(Node head, int key) { //if list is null, return if (head == null) return null; // Find the required node that is to be deleted Node curr = head, prev = new Node(); while (curr.data != key) { if (curr.next == head) { System.out.printf('
Given node ' + key + ' is not found' + “in the list!'); break; } prev = curr; curr = curr.next; } // Check if node is only node if (curr.next == head) { head = null; return head; } // If more than one node, check if it is first node if (curr == head) { prev = head; while (prev.next != head) prev = prev.next; head = curr.next; prev.next = head; } // check if node is last node else if (curr.next == head) { prev.next = head; } else { prev.next = curr.next; } System.out.println('After deleting ' + key + ' the circular list is:'); traverse(head); return head; } // Main code public static void main(String() args){ Node last = null; last = insertInEmpty(last, 30); last = insertAtBegin(last, 20); last = insertAtBegin(last, 10); last = insertAtEnd(last, 40); last = insertAtEnd(last, 60); last = addAfter(last, 50, 40); System.out.println('Circular linked list created is:'); traverse(last); last = deleteNode(last,40); } } Resultado:
A lista circular vinculada criada é:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
Depois de excluir 40, a lista circular é:
10 ==> 20 ==> 30 ==> 50 ==> 60 ==> 10
Vantagens desvantagens
Vamos discutir algumas vantagens e desvantagens da lista ligada circular.
Vantagens:
- Podemos ir a qualquer nó e atravessar de qualquer nó. Só precisamos parar quando visitarmos o mesmo nó novamente.
- Como o último nó aponta para o primeiro nó, ir para o primeiro nó do último nó dá apenas uma única etapa.
Desvantagens:
- Reverter uma lista ligada circular é complicado.
- Como os nós são conectados para formar um círculo, não há marcação adequada para o início ou o fim da lista. Portanto, é difícil encontrar o fim da lista ou controle do loop. Se não for cuidado, uma implementação pode terminar em um loop infinito.
- Não podemos voltar ao nó anterior em uma única etapa. Temos que percorrer a lista inteira primeiro.
Aplicações de lista ligada circular
- A aplicação em tempo real da lista ligada circular pode ser um sistema operacional de multiprogramação em que programa vários programas. Cada programa recebe um carimbo de data / hora dedicado para execução, após o qual os recursos são passados para outro programa. Isso continua continuamente em um ciclo. Esta representação pode ser alcançada de forma eficiente usando uma lista ligada circular.
- Os jogos que são jogados com vários jogadores também podem ser representados usando uma lista ligada circular em que cada jogador é um nó que tem a chance de jogar.
- Podemos usar uma lista ligada circular para representar uma fila circular. Fazendo isso, podemos remover os dois ponteiros frontal e traseiro que são usados para a fila. Em vez disso, podemos usar apenas um ponteiro.
Conclusão
Uma lista ligada circular é uma coleção de nós em que os nós são conectados uns aos outros para formar um círculo. Isso significa que, em vez de definir o próximo ponteiro do último nó como nulo, ele é vinculado ao primeiro nó.
Uma lista ligada circular é útil para representar estruturas ou atividades que precisam ser repetidas várias vezes após um intervalo de tempo específico, como programas em um ambiente de multiprogramação. Também é benéfico para projetar uma fila circular.
Listas circulares vinculadas oferecem suporte a várias operações, como inserção, exclusão e travessias. Assim, vimos as operações em detalhes neste tutorial.
Em nosso próximo tópico sobre estruturas de dados, aprenderemos sobre a estrutura de dados da pilha.
=> Verifique aqui para ver os tutoriais de treinamento A-Z de C ++ aqui.
Leitura recomendada
- Estrutura de dados de lista vinculada em C ++ com ilustração
- Estrutura de dados de lista duplamente vinculada em C ++ com ilustração
- Estrutura de dados da fila em C ++ com ilustração
- Estrutura de pilha de dados em C ++ com ilustração
- Estrutura de dados da fila de prioridade em C ++ com ilustração
- As 15 melhores ferramentas gratuitas de mineração de dados: a lista mais abrangente
- Introdução às estruturas de dados em C ++
- 15 melhores ferramentas ETL em 2021 (uma lista atualizada completa)