Invertir la lista vinculada en C++
Este artículo demostrará cómo revertir una estructura de datos de lista vinculada en C++.
Use la función iterativa para revertir la lista vinculada en C++
Suponemos que el objeto de destino es una lista enlazada individualmente e implementamos fragmentos de código en consecuencia. Al principio, debemos observar las utilidades de funciones básicas en el código del controlador implementado para demostrar el ejemplo.
El nodo de la lista enlazada es una simple struct con un único objeto de datos de string y un puntero al siguiente nodo. También tenemos la función addNewNode que toma dos argumentos, Node* y una referencia a la cadena. La función addNewNode se invoca varias veces en la rutina main para construir un nuevo objeto de lista y almacenar cadenas del vector data_set. La función asigna cada nodo en la memoria dinámica y devuelve el puntero al nodo recién creado.
Otra función útil para nuestra estructura de datos de lista enlazada es printNodes, que se utiliza para enviar datos de cada nodo al flujo cout. El último nos ayudará a verificar vagamente la corrección de la función de inversión. Tenga en cuenta que printNodes mantiene el recuento de nodos durante el recorrido de la lista e imprime el índice de cada elemento. Finalmente, necesitamos desasignar todos los nodos antes de que salga el programa. Este paso no es necesario para la demostración de la función de inversión, pero es importante para cualquier proyecto del mundo real limpiar toda la memoria asignada durante el tiempo de ejecución.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct Node {
struct Node *next{};
string data;
};
struct Node *addNewNode(struct Node *node, string &data) {
auto new_node = new Node;
if (node) node->next = new_node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodes(struct Node *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct Node *tmp, *head = nullptr;
vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
"Meteor Lake"};
head = addNewNode(head, data_set.at(0));
tmp = head;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
}
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
Producción :
node 0 - data: Rocket Lake
node 1 - data: Alder Lake
node 2 - data: Tiger Lake
node 3 - data: Meteor Lake
Una vez que inicializamos una nueva lista vinculada y almacenamos el encabezado de la lista en un puntero separado, podemos usarlo para invertir el contenido. En este caso, implementamos la función reverseList, que acepta un solo argumento Node* y devuelve un nuevo nodo raíz. Al principio, duplicamos el puntero pasado y lo almacenamos como una variable head. También necesitamos dos punteros de tipo Node adicionales para llevar la contabilidad interna durante el bucle while.
El algoritmo de inversión se puede describir de la siguiente manera: Almacenamos el siguiente puntero de nodo en una variable temporal (next) y asignamos el valor nullptr al original. Como resultado, el nodo main original apuntará al nullptr como su próximo nodo en la lista. A continuación, actualizamos la variable head para almacenar el siguiente (el segundo) nodo en la lista original y también guardamos la dirección del nodo principal original en una variable temporal separada.
Repetimos los pasos anteriores hasta que el puntero head se evalúe como nullptr, lo que significaría que se llega al final de la lista. Al final, devolvemos la dirección del nuevo nodo principal almacenado en la variable temporal n. En consecuencia, el programa main llama a la función printNodes para que el usuario compare el contenido de la lista enlazada modificada.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct Node {
struct Node *next{};
string data;
};
struct Node *addNewNode(struct Node *node, string &data) {
auto new_node = new Node;
if (node) node->next = new_node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodes(struct Node *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
Node *reverseList(struct Node *node) {
auto head = node;
Node *n = nullptr;
Node *next = nullptr;
while (head) {
next = head->next;
head->next = n;
n = head;
head = next;
}
return n;
}
int main() {
struct Node *tmp, *head = nullptr;
vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
"Meteor Lake"};
head = addNewNode(head, data_set.at(0));
tmp = head;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
printNodes(reverseList(head));
freeNodes(head);
return EXIT_SUCCESS;
}
Producción :
node 0 - data: Rocket Lake
node 1 - data: Alder Lake
node 2 - data: Tiger Lake
node 3 - data: Meteor Lake
-----------------------------------
node 0 - data: Meteor Lake
node 1 - data: Tiger Lake
node 2 - data: Alder Lake
node 3 - data: Rocket Lake
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++