Eliminar un nodo en una lista vinculada en C++
Este artículo discutirá el método de cómo implementar una función que elimina un nodo dado en una lista enlazada C++.
Implementar una función para eliminar un nodo dado en una lista vinculada
En este artículo, implementamos una lista enlazada individualmente desde cero sin utilizar los contenedores de STL. Por lo tanto, necesitamos definir algunas funciones necesarias para administrar los nodos en una lista vinculada.
El elemento insertNode es la función principal que debe invocarse para crear una nueva lista vinculada. Como necesitamos almacenar el encabezado de la lista, el insertNode devuelve el puntero al nodo de tipo ListNode. Esta última es la representación mínima del nodo de la lista enlazada. Solo contiene un puntero al siguiente nodo y al objeto de datos string.
Durante la prueba y demostración del programa, es importante tener algunas funciones de utilidad para mostrar algunos mensajes en la consola del usuario. En este caso, el elemento printNodes se utiliza para imprimir todos los nodos en la estructura de lista dada. Además, necesitamos desasignar cada nodo existente en la lista al salir del programa usando la función freeNodes al asignar nuevos nodos en la memoria dinámica.
Una vez que construimos una lista con los datos arbitrarios como se muestra en la función main del siguiente fragmento de código, estamos listos para invocar deleteNode, que implementa la operación de eliminación de nodos. La eliminación de un nodo requiere que se manejen varios casos de esquina en él. Es decir, el escenario en el que el nodo dado es el mismo que el encabezado de la lista y el otro cuando el nodo dado es el único nodo en la lista.
En el último escenario, podemos simplemente llamar al operador remove en el puntero del nodo y regresar de la función. Aunque es importante asignar nullptr a la dirección porque esto nos ayudará a agregar nuevos elementos a la misma variable head en la función principal.
Por otro lado, eliminar el nodo principal cuando hay otros nodos en la lista es relativamente complicado. Tenemos que copiar el contenido del segundo nodo al nodo principal y eliminar el anterior. Observe que cada caso devuelve el valor EXIT_SUCCESS para indicar una llamada de función exitosa.
#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;
}
Producción :
node 0 - data: Xenial
node 1 - data: Artful
-----------------------------------
node 0 - data: Artful
El código de función restante implementa el caso normal, donde el nodo dado se desengancha de la cadena de lista y luego se desasigna usando el operador delete. Sin embargo, tenga en cuenta que esta operación requiere que se encuentre el nodo anterior, que es la operación de tiempo lineal para cada nodo excepto el del encabezado de la lista. Por lo general, se debe almacenar el final de la lista en la estructura de la lista vinculada para garantizar la eliminación de tiempo constante para el final de la lista.
El siguiente fragmento de código muestra un escenario de función main diferente, donde un nodo se elimina del medio de la 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;
}
Producción :
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 FacebookArtículo relacionado - C++ Data Structure
- Destructor de árbol de búsqueda binaria de C++
- Eliminar un nodo del árbol binario de búsqueda en C++
- Estructura de datos de pila usando una lista enlazada en C++
- Implementar Inorder Traversal para el árbol binario de búsqueda en C++
- Implementar matriz circular en C++
- Implementar una estructura de datos de cola usando una lista vinculada en C++