Implementación de listas enlazadas en C++
Esta publicación proporciona una descripción general de algunas técnicas disponibles para implementar una lista vinculada en el lenguaje de programación C++.
Sabemos que cada nodo de una lista enlazada contiene un solo campo de datos y un puntero al siguiente nodo de la lista.
|
1 2 3 4 5 6 7 |
// Un nodo de lista enlazada class Node { public: int key; // campo de datos Node* next; // puntero al siguiente nodo }; |
Los nodos de la lista enlazada se asignan en la memoria del heap. Podemos usar el operador new en C++ para la asignación de memoria dinámica y el delete operador para desasignar la memoria asignada.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Función de utilidad para devolver un nuevo nodo de lista enlazada del heap Node* newNode(int key) { // asignar el nuevo nodo en un heap usando el operador new y establecer sus datos Node* node = new Node; node->key = key; // establece el puntero `.next` del nuevo nodo para que apunte a nulo node->next = nullptr; return node; } |
Hay varios métodos para construir una lista enlazada individualmente. Cada uno se cubre en detalle a continuación:
1. Método ingenuo
Una solución simple sería asignar memoria para todos los nodos individuales de la lista vinculada, establecer sus datos y reorganizar sus punteros para construir la lista completa.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <iostream> using namespace std; // Un nodo de lista enlazada class Node { public: int key; // campo de datos Node* next; // puntero al siguiente nodo }; // Función de utilidad para devolver un nuevo nodo de lista enlazada del heap Node* newNode(int key) { // asignar un nuevo nodo en un heap y configurar sus datos Node* node = new Node; node->key = key; // El puntero `.next` del nuevo nodo no apunta a nada node->next = nullptr; return node; } // Función para la implementación de listas enlazadas que contienen tres nodos Node* constructList() { // construye tres nodos de lista enlazados Node* first = newNode(1); Node* second = newNode(2); Node* third = newNode(3); // reorganizar los punteros para construir una lista Node* head = first; first->next = second; second->next = third; // devuelve un puntero al primer nodo de la lista return head; } // Función auxiliar para imprimir una lista enlazada void printList(Node* head) { Node* ptr = head; while (ptr) { cout << ptr->key << " -> "; ptr = ptr->next; } cout << "nullptr"; } int main() { // `head` apunta al primer nodo (también conocido como nodo principal) de una lista enlazada Node *head = constructList(); // imprimir lista enlazada printList(head); return 0; } |
2. Línea única
Podemos escribir el código anterior en una sola línea pasando el siguiente nodo como argumento al newNode() función:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <iostream> using namespace std; // Un nodo de lista enlazada class Node { public: int key; // campo de datos Node* next; // puntero al siguiente nodo }; // Función de utilidad para devolver un nuevo nodo de lista enlazada del heap Node* newNode(int key, Node* next) { // asignar un nuevo nodo en un heap y configurar sus datos Node* node = new Node; node->key = key; // establece el puntero `.next` del nuevo nodo para que apunte al actual // primer nodo de la lista. node->next = next; return node; } // Función para la implementación de listas enlazadas que contienen tres nodos Node* constructList() { Node* head = newNode(1, newNode(2, newNode(3, nullptr))); return head; } // Función auxiliar para imprimir una lista enlazada void printList(Node* head) { Node* ptr = head; while (ptr) { cout << ptr->key << " -> "; ptr = ptr->next; } cout << "nullptr"; } int main() { // `head` apunta al primer nodo (también conocido como nodo principal) de una lista enlazada Node *head = constructList(); // imprimir lista enlazada printList(head); return 0; } |
3. Método genérico
Ambos métodos anteriores no son prácticos cuando el número total de nodos aumenta en la lista enlazada. Si las claves se dan en cualquier contenedor, como una array, un vector o un conjunto, podemos construir fácilmente una lista enlazada recorriendo el contenedor, como se muestra a continuación:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <iostream> #include <vector> using namespace std; // Un nodo de lista enlazada class Node { public: int key; // campo de datos Node* next; // puntero al siguiente nodo }; // Función de utilidad para devolver un nuevo nodo de lista enlazada del heap Node* newNode(int key, Node* next) { // asignar un nuevo nodo en un heap y configurar sus datos Node* node = new Node; node->key = key; // establece el puntero `.next` del nuevo nodo para que apunte al actual // primer nodo de la lista. node->next = next; return node; } // Función para la implementación de listas enlazadas a partir de un conjunto dado de claves Node* constructList(vector<int> const &keys) { Node* head, *node = nullptr; // comienza desde el final de la array for (int i = keys.size() - 1; i >= 0; i--) { node = newNode(keys[i], node); head = node; } return head; } // Función auxiliar para imprimir una lista enlazada void printList(Node* head) { Node* ptr = head; while (ptr) { cout << ptr->key << " -> "; ptr = ptr->next; } cout << "nullptr"; } int main() { // teclas de entrada (en orden inverso) vector<int> keys = { 4, 3, 2, 1 }; // construir lista enlazada Node *head = constructList(keys); // imprimir lista enlazada printList(head); return 0; } |
4. Solución estándar
La solución estándar agrega un solo nodo al extremo principal de cualquier lista. Esta función se llama push() ya que estamos agregando el enlace a la cabecera, haciendo que una lista se parezca un poco a una stack.
Sabemos que C++ tiene su propio & argumento Función para implementar parámetros de referencia. Si añadimos un & al tipo de parámetro, el compilador automáticamente hará que el parámetro opere por referencia sin alterar el tipo del argumento.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include <iostream> #include <vector> using namespace std; // Un nodo de lista enlazada class Node { public: int key; // campo de datos Node* next; // puntero al siguiente nodo }; /* push() en C++ — simplemente agregamos `&` al lado derecho de la cabeza tipo de parámetro, y el compilador hace que ese parámetro funcione por referencia. Por lo tanto, este código cambia la memoria de la persona que llama, pero no se requieren usos adicionales de `*`. necesario: accedemos a "head" directamente, y el compilador lo hace cambiar la referencia de nuevo a la persona que llama. */ void push(Node* &headRef, int key) { // asignar un nuevo nodo en un heap y configurar sus datos Node* node = new Node; node->key = key; // establece el puntero `.next` del nuevo nodo para que apunte al actual // primer nodo de la lista. // no es necesario el uso extra de `*` en el encabezado — el compilador // se encarga de eso detrás de escena node->next = headRef; // cambia el puntero principal para que apunte al nuevo nodo, para que sea // ahora el primer nodo de la lista. headRef = node; } // Función para la implementación de listas enlazadas a partir de un conjunto dado de claves Node* constructList(vector<int> const &keys) { Node* head = nullptr; // comienza desde el final de la array for (int i = keys.size() - 1; i >= 0; i--) { // Tenga en cuenta que no es necesario un uso adicional de `&`: el compilador toma // cuídalo aquí también. Estas llamadas están cambiando la cabeza. push(head, keys[i]); } return head; } // Función auxiliar para imprimir una lista enlazada void printList(Node* head) { Node* ptr = head; while (ptr) { cout << ptr->key << " -> "; ptr = ptr->next; } cout << "nullptr"; } int main() { // teclas de entrada (en orden inverso) vector<int> keys = { 4, 3, 2, 1 }; // construir lista enlazada Node *head = constructList(keys); // imprimir lista enlazada printList(head); return 0; } |
5. Haz que el puntero principal sea global
Podemos construir una lista enlazada haciendo que el puntero principal sea global, pero este enfoque no se recomienda ya que variables globales generalmente se consideran malas prácticas.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <iostream> #include <vector> using namespace std; // Un nodo de lista enlazada class Node { public: int key; Node* next; }; // Puntero de cabeza global Node* head = nullptr; // Toma una lista y un valor de datos, crea un nuevo enlace con el dado // datos y los empuja al frente de la lista. void push(int key) { // asignar un nuevo nodo en un heap y configurar sus datos Node* node = new Node; node->key = key; // establece el puntero `.next` del nuevo nodo para que apunte al actual // nodo principal de la lista. node->next = head; // cambia el puntero principal para que apunte al nuevo nodo, para que sea // ahora el primer nodo de la lista. head = node; } // Función para la implementación de listas enlazadas a partir de un conjunto dado de claves void constructList(vector<int> const &keys) { // comienza desde el final de la array for (int i = keys.size() - 1; i >= 0; i--) { push(keys[i]); } } // Función auxiliar para imprimir la lista enlazada global `head` void printList() { Node* ptr = head; while (ptr) { cout << ptr->key << " -> "; ptr = ptr->next; } cout << "nullptr"; } int main() { // teclas de entrada (en orden inverso) vector<int> keys = { 4, 3, 2, 1 }; // construir lista enlazada constructList(keys); // imprimir lista enlazada printList(); return 0; } |
6. Regresar la cabeza del push() función
Otro enfoque común que siguen muchos programadores es devolver el nodo principal del push() función y actualizar la cabeza en la persona que llama. Esto se demuestra a continuación:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <iostream> #include <vector> using namespace std; // Un nodo de lista enlazada class Node { public: int key; // campo de datos Node* next; // puntero al siguiente nodo }; /* Toma una lista y un valor de datos, crea un nuevo enlace con los datos dados y lo empuja al frente de la lista. */ Node* push(Node* head, int key) { // asignar un nuevo nodo en un heap y configurar sus datos Node* node = new Node; node->key = key; // establece el puntero `.next` del nuevo nodo para que apunte al actual // primer nodo de la lista. node->next = head; // devuelve el nuevo nodo, por lo que se convierte en el primer nodo de la lista return node; } // Función para la implementación de listas enlazadas a partir de un conjunto dado de claves Node* constructList(vector<int> const &keys) { Node* head = nullptr; // comienza desde el final de la array for (int i = keys.size() - 1; i >= 0; i--) { head = push(head, keys[i]); // actualice el encabezado aquí } return head; } // Función auxiliar para imprimir una lista enlazada void printList(Node* head) { Node* ptr = head; while (ptr) { cout << ptr->key << " -> "; ptr = ptr->next; } cout << "nullptr"; } int main() { // teclas de entrada (en orden inverso) vector<int> keys = { 4, 3, 2, 1 }; // construir lista enlazada Node *head = constructList(keys); // imprimir lista enlazada printList(head); return 0; } |
Sigue leyendo:
Lista enlazada – Inserción en la cola | Implementación de C, Java y Python
Ver también:
Referencias: http://cslibrary.stanford.edu/103/LinkedListBasics.pdf