Implementar uma estrutura de dados de lista ligada circular em C++
- Implemente uma lista ligada unicamente circular com funções de membro para adicionar novos elementos no final e para imprimir elementos em C++
- Implemente o destruidor e a função de membro para inserir novos elementos no início da lista em C++
![Implementar uma estrutura de dados de lista ligada circular em C++](/img/Cpp/feature-image---circular-linked-list-in-cpp.webp)
Este artigo explicará como implementar uma estrutura de dados de lista ligada circular em C++.
Implemente uma lista ligada unicamente circular com funções de membro para adicionar novos elementos no final e para imprimir elementos em C++
Uma lista ligada circular pode ser caracterizada como uma lista ligada em que o último nó aponta para o topo da lista. Essencialmente, os nós da lista formam um círculo e não há nullptr
para demarcar o final da lista. Você pode utilizar listas circulares vinculadas para construir estruturas de dados em estilo de fila. O recurso de circularidade pode ser adicionado à lista duplamente vinculada e a uma lista vinculada individualmente.
Nesse caso, vamos implementar o último. Lembre-se de que precisamos definir uma estrutura de nó que inclui um ponteiro para o próximo nó e um elemento de dados para construir uma lista unida individualmente. O objeto struct ListNode
representa um único nó para nossa implementação e armazena um único objeto string
denominado data
, que servirá como os dados do elemento para este exemplo. Observe que é possível armazenar qualquer objeto definido de forma personalizada em um nó e, se o objeto for relativamente maior, é melhor incluí-lo como um ponteiro.
Uma vez que temos uma estrutura de um único nó, podemos definir uma classe CircularList
, que tem apenas duas funções-membro para começar. Geralmente, uma lista ligada circular deve manter o controle do cabeçalho da lista ou de seu final; entretanto, o implementador geralmente é livre para tomar a decisão de design da classe com base em suas necessidades. Além disso, a classe CircularList
armazena dois ponteiros separados para representar o início e o final da lista.
O ponteiro que armazena o início / fim da lista pode ser um nó fictício ou um nó real com os dados. Neste exemplo, escolhemos projetar a classe CircularList
para não ter ponteiros fictícios. Definimos um construtor para aceitar um parâmetro string
para inicializar o primeiro nó na lista circular. Observe que as escolhas de design durante a definição da classe geralmente afetam variáveis diferentes, que devem ser consideradas com base no problema subjacente. Assim, a implementação a seguir pretende ser simples para explicar o conceito de listas circulares vinculadas.
Uma vez que o objeto CircularList
é inicializado usando o construtor, podemos adicionar novos elementos usando a função de membro insertNodeEnd
. Este último aceita o parâmetro string
e constrói um novo elemento no final da lista. A função insertNodeEnd
aloca novos elementos com o operador new
e modifica os ponteiros de acordo para inserir o nó logo após o final da lista. Ele também atualiza o membro de dados final
para apontar para um nó recém-alocado.
Outra função membro definida no próximo exemplo é o printNodes
, que itera através da lista para imprimir seu conteúdo e não leva nenhum argumento. Agora, para demonstrar melhor o uso desta estrutura, precisamos de algum código de driver na função main
. Escolhemos inicializar um vetor
de strings arbitrárias para depois ser inserido no objeto CircularList
usando o loop for
. Finalmente, invocamos uma função printNodes
para exibir o conteúdo da lista no terminal.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class CircularList {
public:
explicit CircularList(string data) {
head = new ListNode;
head->next = head;
head->data = std::move(data);
end = head;
};
ListNode *insertNodeEnd(string data);
void printNodes();
private:
ListNode *head = nullptr;
ListNode *end = nullptr;
};
ListNode *CircularList::insertNodeEnd(string data) {
auto new_node = new ListNode;
new_node->next = end->next;
new_node->data = std::move(data);
end->next = new_node;
end = end->next;
return new_node;
}
void CircularList::printNodes() {
auto count = 0;
auto tmp = head;
while (tmp != end) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
cout << "node " << count << " - data: " << tmp->data << endl;
}
int main() {
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
CircularList clist("Xenial");
for (const auto &item : data_set) {
clist.insertNodeEnd(item);
}
clist.printNodes();
return EXIT_SUCCESS;
}
Resultado:
node 0 - data : Xenial node 1 - data : Precise node 2 - data : Quantal node 3 -
data
: Saucy node 4 -
data : Raring
Implemente o destruidor e a função de membro para inserir novos elementos no início da lista em C++
Observe que o fragmento de código anterior tem um grande problema de não ter um destruidor definido; isso implica que o programa que utiliza a classe CircularList
vazará memória, uma vez que os nós criados na memória dinâmica não são liberados até a saída do programa.
A solução para este problema é implementar um destruidor que irá percorrer toda a lista e desalocar todos os nós usando o operador delete
. Assim, não precisamos nos preocupar em liberar a memória da lista manualmente. Ele será automaticamente liberado assim que o objeto CircularList
atingir o final do escopo.
Outra função útil para implementar é aquela que insere um novo elemento no topo da lista; o comando insertNodeHead
é projetado para fazer exatamente isso. Leva apenas um argumento string
para ser armazenado e retorna o ponteiro para o nó recém-alocado. Observe que o valor de retorno para as funções insertNodeEnd
e insertNodeHead
é outra opção de design, que é implementada de forma diferente conforme o programador decide. O fragmento de código a seguir inclui o código de driver semelhante na função main
para testar e mostrar o uso da classe CircularList
.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class CircularList {
public:
explicit CircularList(string data) {
head = new ListNode;
head->next = head;
head->data = std::move(data);
end = head;
};
ListNode *insertNodeEnd(string data);
ListNode *insertNodeHead(string data);
void printNodes();
~CircularList();
private:
ListNode *head = nullptr;
ListNode *end = nullptr;
};
ListNode *CircularList::insertNodeEnd(string data) {
auto new_node = new ListNode;
new_node->next = end->next;
new_node->data = std::move(data);
end->next = new_node;
end = end->next;
return new_node;
}
ListNode *CircularList::insertNodeHead(string data) {
auto new_node = new ListNode;
new_node->next = end->next;
new_node->data = std::move(data);
end->next = new_node;
head = end->next;
return new_node;
}
CircularList::~CircularList() {
while (head != end) {
auto tmp = head;
head = head->next;
delete tmp;
}
delete head;
}
void CircularList::printNodes() {
auto count = 0;
auto tmp = head;
while (tmp != end) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
cout << "node " << count << " - data: " << tmp->data << endl;
}
int main() {
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
CircularList clist("Xenial");
for (const auto &item : data_set) {
clist.insertNodeEnd(item);
}
clist.printNodes();
cout << " ----------------------------------- " << endl;
clist.insertNodeHead("Bionic");
clist.insertNodeEnd("Zeisty");
clist.printNodes();
return EXIT_SUCCESS;
}
Resultado:
node 0 - data : Xenial node 1 - data : Precise node 2 - data : Quantal node 3 -
data
: Saucy node 4 -
data
: Raring-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
data : Bionic node 1 - data : Xenial node 2 - data : Precise node 3 -
data
: Quantal node 4 -
data : Saucy node 5 - data : Raring node 6 - data : Zeisty
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn FacebookArtigo relacionado - C++ Data Structure
- Estrutura de pilha de dados usando lista vinculada em C++
- Excluir um nó da árvore binária de busca em C++
- Implementar Inorder Traversal para árvore binária de busca em C++
- Implementar Matriz Circular em C++
- Implementar uma estrutura de dados de fila usando lista vinculada em C++
- Inserção de árvore binária de busca em C++