Insertar un nodo en una lista enlazada individualmente C++
- Implementar una función para insertar un nodo al final de una lista vinculada
- Implementar una función para insertar un nodo después de un nodo dado en una lista vinculada
- Implementar una función para insertar un nodo al comienzo de una lista vinculada
Este artículo explica el método de cómo insertar un nuevo nodo en una lista enlazada individualmente en C++.
Implementar una función para insertar un nodo al final de una lista vinculada
Las listas enlazadas son estructuras de datos lineales que constan de nodos que se apuntan entre sí, de forma secuencial. En este artículo, nos enfocamos más en una estructura de lista enlazada e implementamos múltiples operaciones de inserción de manera correspondiente.
En una lista enlazada individualmente, tenemos un objeto (s) de datos y un puntero al siguiente nodo de la lista. Definimos una estructura de nodo llamada ListNode y dos funciones auxiliares (freeNodes y printNodes) para demostrar mejor las operaciones de inserción de listas. Tenga en cuenta que la complejidad del tiempo de la operación de inserción varía según la posición en la que estamos insertando un nodo. Por ejemplo, la inserción al final de la lista toma un tiempo lineal si se desconoce el final de la lista.
Por otro lado, insertar un nuevo nodo al principio siempre lleva un tiempo constante. El siguiente código demuestra la función insertNodeEnd, que puede tratarse como la función principal para construir una lista. Toma el encabezado de la lista como primer parámetro y los datos de la string que deben almacenarse en un nuevo nodo. La función puede crear el primer elemento de la lista y agregar nuevos elementos al final. La función asigna nuevos nodos en la memoria de almacenamiento libre. Por tanto, la función freeNodes es necesaria para liberar toda la memoria antes de salir del programa.
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNodeEnd(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;
}
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;
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
head = insertNodeEnd(head, data_set.at(0));
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
insertNodeEnd(head, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
insertNodeEnd(head, "Utopic");
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
Producción :
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
-----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic
Implementar una función para insertar un nodo después de un nodo dado en una lista vinculada
Insertar un nodo en el medio de la lista generalmente toma un tiempo constante más la complejidad de tiempo del algoritmo de búsqueda utilizado para encontrar la posición dada. Sin embargo, asumimos que la función de búsqueda se implementa por separado y construimos la función insertNodeAfter de modo que la posición del nodo de destino debe proporcionarse como primer argumento.
Dado que la función insertNodeEnd devuelve el puntero a un nodo recién agregado, utilizamos su valor de retorno para demostrar la operación de insertNodeAfter. Tenga en cuenta que necesitaría una función de búsqueda separada para inserciones de posiciones arbitrarias e incluso podría necesitar una estructura de datos externa para implementar una operación de búsqueda más rápida en una lista vinculada.
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNodeEnd(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;
}
struct ListNode *insertNodeAfter(struct ListNode *prev, string data) {
if (!prev) return nullptr;
auto new_node = new ListNode;
new_node->next = nullptr;
new_node->data = std::move(data);
prev->next = new_node;
return new_node;
}
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;
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
head = insertNodeEnd(head, data_set.at(0));
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
insertNodeEnd(head, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
auto iter = insertNodeEnd(head, "Utopic");
printNodes(head);
cout << " ----------------------------------- " << endl;
insertNodeAfter(iter, "Xenial");
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
Producción :
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
-----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic
-----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic
node 5 - data: Xenial
Implementar una función para insertar un nodo al comienzo de una lista vinculada
Otra operación de inserción útil para la lista enlazada individualmente es agregar un nuevo nodo al principio. Esta función tiene el mejor tiempo de ejecución O(1) ya que el encabezado de la lista siempre se almacena para acceder a la propia lista. La función insertNodeFront toma la referencia a un puntero raíz y al objeto string que debe almacenarse en el nodo. El proceso se implementa para que pueda usarlo para inicializar una nueva lista vinculada, así como la inserción frontal.
Alternativamente, puede reescribir la función para asignar un nuevo nodo cuando el argumento root no es nullptr. De lo contrario, devuelva nullptr para indicar que la función falló. La interfaz de estas funciones depende de las necesidades de los programadores y de la estructura del ListNode.
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNodeEnd(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;
}
struct ListNode *insertNodeFront(struct ListNode *&root, string data) {
auto new_node = new ListNode;
if (root) {
new_node->next = root;
new_node->data = std::move(data);
root = new_node;
return root;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
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;
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
head = insertNodeEnd(head, data_set.at(0));
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
insertNodeEnd(head, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
insertNodeFront(head, "Bionic");
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
Producción :
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
-----------------------------------
node 0 - data: Bionic
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring
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++