Excluir um nó em uma lista vinculada em C++
Este artigo irá discutir o método de como implementar uma função que exclui um determinado nó em uma lista vinculada C++.
Implementar uma função para excluir um determinado nó em uma lista vinculada
Neste artigo, implementamos uma lista vinculada única do zero, sem utilizar os contêineres do STL. Portanto, precisamos definir algumas funções necessárias para gerenciar os nós em uma lista vinculada.
O elemento insertNode é a função principal que precisa ser chamada para criar uma nova lista vinculada. Uma vez que precisamos armazenar o cabeçalho da lista, o insertNode retorna o ponteiro para o nó do tipo ListNode. O último é a representação mínima do nó da lista vinculada. Ele contém apenas um ponteiro para o próximo nó e o objeto de dados string.
Durante o teste e a demonstração do programa, é importante ter algumas funções de utilitário para exibir algumas mensagens no console do usuário. Neste caso, o elemento printNodes é utilizado para imprimir todos os nós na estrutura de lista dada. Além disso, precisamos desalocar cada nó existente na lista na saída do programa usando a função freeNodes ao alocar novos nós na memória dinâmica.
Uma vez que construímos uma lista com os dados arbitrários, conforme mostrado na função main do seguinte trecho de código, estamos prontos para invocar deleteNode, que implementa a operação de remoção de nó. A remoção de um nó requer que vários casos extremos sejam tratados nele. Ou seja, o cenário em que o nó fornecido é o mesmo que o cabeçalho da lista e o outro quando o nó fornecido é o único na lista.
No último cenário, podemos apenas chamar o operador delete no ponteiro do nó e retornar da função. Embora seja importante atribuir nullptr ao endereço, porque isso nos ajudará a adicionar novos elementos à mesma variável head na função principal.
Por outro lado, remover o nó principal quando houver outros nós na lista é relativamente complicado. Temos que copiar o conteúdo do segundo nó para o nó principal e deletar o anterior. Observe que cada caso retorna o valor EXIT_SUCCESS para indicar uma chamada de função bem-sucedida.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNode(struct ListNode *root, string data) {
auto new_node = new ListNode;
if (root) {
while (root->next) root = root->next;
new_node->next = nullptr;
new_node->data = std::move(data);
root->next = new_node;
return root->next;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
int deleteNode(struct ListNode *root, struct ListNode *node) {
if (node == nullptr || root == nullptr) return EXIT_FAILURE;
if (root == node) {
if (root->next == nullptr) {
delete node;
root = nullptr;
return EXIT_SUCCESS;
}
node = root->next;
root->data = root->next->data;
root->next = root->next->next;
delete node;
return EXIT_SUCCESS;
}
auto prev = root;
while (prev->next != node && prev->next != nullptr) {
prev = prev->next;
}
prev->next = node->next;
delete node;
return EXIT_SUCCESS;
}
void freeNodes(struct ListNode *root) {
struct ListNode *tmp = nullptr;
while (root) {
tmp = root;
root = root->next;
delete tmp;
}
}
void printNodes(struct ListNode *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct ListNode *head = nullptr;
head = insertNode(head, "Xenial");
insertNode(head, "Artful");
printNodes(head);
cout << " ----------------------------------- " << endl;
deleteNode(head, head);
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
Resultado:
node 0 - data : Xenial node 1 -
data
: Artful-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
data : Artful
O código de função restante implementa o caso regular, em que o nó fornecido é desconectado da cadeia da lista e então desalocado usando o operador delete. Observe, porém, que esta operação requer que o nó anterior seja encontrado, que é a operação de tempo linear para cada nó, exceto do cabeçalho da lista. Normalmente, deve-se armazenar o final da lista na estrutura da lista vinculada para garantir a remoção de tempo constante para o final da lista.
O fragmento de código a seguir demonstra um cenário de função main diferente, em que um nó é removido do meio da lista.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNode(struct ListNode *root, string data) {
auto new_node = new ListNode;
if (root) {
while (root->next) root = root->next;
new_node->next = nullptr;
new_node->data = std::move(data);
root->next = new_node;
return root->next;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
int deleteNode(struct ListNode *root, struct ListNode *node) {
if (node == nullptr || root == nullptr) return EXIT_FAILURE;
if (root == node) {
if (root->next == nullptr) {
delete node;
root = nullptr;
return EXIT_SUCCESS;
}
node = root->next;
root->data = root->next->data;
root->next = root->next->next;
delete node;
return EXIT_SUCCESS;
}
auto prev = root;
while (prev->next != node && prev->next != nullptr) {
prev = prev->next;
}
prev->next = node->next;
delete node;
return EXIT_SUCCESS;
}
void freeNodes(struct ListNode *root) {
struct ListNode *tmp = nullptr;
while (root) {
tmp = root;
root = root->next;
delete tmp;
}
}
void printNodes(struct ListNode *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct ListNode *head = nullptr;
head = insertNode(head, "Xenial");
auto iter = insertNode(head, "Bionic");
insertNode(head, "Artful");
printNodes(head);
cout << " ----------------------------------- " << endl;
deleteNode(head, iter);
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
Resultado:
node 0 - data : Xenial node 1 - data : Bionic node 2 -
data
: Artful-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
data : Xenial node 1 - data : Artful
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++