Copiar constructor de lista enlazada en C++
Este breve artículo trata sobre la implementación basada en C++ de la lista enlazada que tiene un constructor de copia profunda.
Copiar constructor en C++
Se llama a un constructor de copia para inicializar un objeto usando otro objeto de la misma clase. El constructor de copia se llama en múltiples situaciones como:
- Cuando se copia un objeto usando otro objeto.
- Cuando el objeto se devuelve como un valor de la función.
- Cuando se pasa un objeto como valor a una función.
En cada clase, siempre hay un constructor de copia predeterminado, pero no realiza una copia profunda sino una copia superficial. Solo la dirección del puntero se copia con una copia superficial, y ambos objetos (es decir, el que llama y los objetos pasados) apuntan a la misma memoria.
Por el contrario, en la copia profunda, los valores de los miembros de datos se copian en los miembros de datos del objeto de destino.
Lista enlazada en C++
La estructura de datos de lista enlazada almacena datos en forma de nodos de datos que pueden crecer dinámicamente. No requiere memoria contigua, por lo que puede almacenarse eficientemente en cualquier lugar de la memoria.
Implementación de listas enlazadas en C++
Empecemos a implementar la lista enlazada. Primero, necesitamos crear una clase para obtener nodos de datos:
template <class T>
class Node {
public:
T info;
Node<T>* next;
Node() { next = 0; }
Node(T val) {
info = val;
next = 0;
}
};
La clase Node tiene dos miembros: uno para almacenar datos (es decir, info), y el otro es el puntero a la clase en sí para almacenar la dirección del siguiente nodo. La clase se crea con una plantilla para que se pueda crear una lista de cualquier tipo de datos.
La implementación anterior proporciona dos constructores. El primero es el constructor predeterminado y el otro está parametrizado.
Echemos un vistazo a la clase de plantilla para la lista enlazada:
template <class T>
class LSLL {
private:
Node<T>* head;
public:
LSLL() { head = 0; }
};
La clase LSLL tiene solo un puntero a la clase Nodo, que se utilizará para contener la dirección del primer nodo de la lista enlazada.
Para proporcionar al usuario la funcionalidad de copiar profundamente un objeto de lista enlazada a otro, debemos proporcionar una implementación de constructor de copia definida por el usuario como se indica a continuación:
LSLL(LSLL& PassedObj) {
if (PassedObj.head == NULL) {
head = NULL;
} else {
// copy all nodes of PassedObj to the caller object
// attach first node to the head of the caller object
Node<T>* newNode = new Node<T>();
newNode->info = PassedObj.head->info;
newNode->next = NULL;
head = newNode;
// Now deep-copy all the remaining nodes of the Passed linked list object
Node<T>* PassedItr = PassedObj.head->next;
Node<T>* CallerItr = head;
while (PassedItr != NULL) {
CallerItr->next = new Node<T>();
CallerItr->next->info = PassedItr->info;
CallerItr->next->next = NULL;
CallerItr = CallerItr->next; // move to newly added node
PassedItr = PassedItr->next; // move one node further
}
}
}
El segmento de código anterior crea una copia profunda del primer nodo del objeto pasado y lo adjunta a la cabeza del objeto de la lista de llamadas. Después de eso, todos los nodos restantes del objeto pasado se copian en profundidad y se adjuntan al nodo de la lista vinculada a la persona que llama.
Tengamos una vista cognitiva de toda la implementación:
#include <iostream>
using namespace std;
template <class T>
class Node {
public:
T info;
Node<T>* next;
Node() { next = NULL; }
Node(T val) {
info = val;
next = NULL;
}
};
template <class T>
class LSLL {
private:
Node<T>* head;
public:
LSLL() { head = NULL; }
LSLL(LSLL& PassedObj) {
if (PassedObj.head == NULL) {
head = NULL;
} else {
// copy all nodes of PassedObj to the caller object
// attach first node to the head of the caller object
Node<T>* newNode = new Node<T>();
newNode->info = PassedObj.head->info;
newNode->next = NULL;
head = newNode;
// Now deep-copy all the remaining nodes of the Passed linked list object
Node<T>* PassedItr = PassedObj.head->next;
Node<T>* CallerItr = head;
while (PassedItr != NULL) {
CallerItr->next = new Node<T>();
CallerItr->next->info = PassedItr->info;
CallerItr->next->next = NULL;
CallerItr = CallerItr->next; // move to newly added node
PassedItr = PassedItr->next; // move one node further
}
}
}
void insertAtHead(T val) {
Node<T>* x = new Node<T>(val);
x->next = head;
head = x;
}
void displayAll() {
Node<T>* x = head;
{
while (x != 0) {
cout << x->info << endl;
x = x->next;
}
}
}
int isEmpty() {
if (head == 0) return 1;
return 0;
}
void insetAtTail(T val) {
Node<T>* x = head;
if (isEmpty()) {
insertAtHead(val);
return;
}
while (x->next != 0) {
x = x->next;
}
x->next = new Node<T>(val);
}
void insertAfter(T key, T val) {
if (isEmpty()) return;
Node<T>* x = head;
while (x != 0 && x->info == key) x = x->next;
if (!x) return;
Node<T>* temp = new Node<T>(val);
temp->next = x->next;
x->next = x;
}
};
int main() {
LSLL<int> list;
list.insertAtHead(200);
list.insertAtHead(100);
list.insetAtTail(300);
list.displayAll();
LSLL<int> list2(list);
cout << "List2: " << endl;
list2.displayAll();
return 0;
}
El código del controlador principal primero crea un objeto de list, inserta tres nodos en él y llama a la función displayAll. Después de eso, crea un nuevo objeto de lista enlazada, list2 y llama a su constructor de copia parametrizado con la list como argumento.
Tenga en cuenta que el objeto list2 es el objeto que llama, mientras que list es el objeto pasado.
Producción :
100
200
300
List2:
100
200
300
Husnain is a professional Software Engineer and a researcher who loves to learn, build, write, and teach. Having worked various jobs in the IT industry, he especially enjoys finding ways to express complex ideas in simple ways through his content. In his free time, Husnain unwinds by thinking about tech fiction to solve problems around him.
LinkedIn