simples - ¿Cuál es el motivo para usar un doble puntero al agregar un nodo en una lista vinculada?
operaciones con listas enlazadas (13)
Los dos ejemplos de código a continuación añaden un nodo en la parte superior de una lista vinculada. Pero mientras que el primer ejemplo de código usa un doble puntero, el segundo ejemplo de código usa un solo puntero
ejemplo de código 1:
struct node* push(struct node **head, int data)
{
struct node* newnode = malloc(sizeof(struct node));
newnode->data = data;
newnode->next = *head;
return newnode;
}
push(&head,1);
ejemplo de código 2:
struct node* push(struct node *head, int data)
{
struct node* newnode = malloc(sizeof(struct node));
newnode->data = data;
newnode->next = head;
return newnode;
}
push(head,1)
Ambas estrategias funcionan Sin embargo, muchos programas que usan una lista vinculada usan un doble puntero para agregar un nuevo nodo. Sé lo que es un doble puntero. Pero si un único puntero sería suficiente para agregar un nuevo nodo, ¿por qué muchas implementaciones se basan en dobles punteros?
¿Hay algún caso en el que un solo puntero no funcione, por lo que debemos buscar un doble puntero?
Algunas implementaciones pasan un puntero a un parámetro de puntero para permitir cambiar el puntero de la cabeza directamente en lugar de devolver la nueva. Por lo tanto, podrías escribir:
// note that there''s no return value: it''s not needed
void push(struct node** head, int data)
{
struct node* newnode = malloc(sizeof(struct node));
newnode->data=data;
newnode->next=*head;
*head = newnode; // *head stores the newnode in the head
}
// and call like this:
push(&head,1);
La implementación que no toma un puntero al puntero de la cabeza debe devolver la nueva cabeza, y la persona que llama es responsable de actualizarla por sí misma:
struct node* push(struct node* head, int data)
{
struct node* newnode = malloc(sizeof(struct node));
newnode->data=data;
newnode->next=head;
return newnode;
}
// note the assignment of the result to the head pointer
head = push(head,1);
Si no realiza esta asignación al llamar a esta función, tendrá fugas en los nodos que asigna con malloc, y el puntero de la cabeza siempre apuntará al mismo nodo.
La ventaja debe ser clara ahora: con el segundo, si la persona que llama olvida asignar el nodo devuelto al puntero de la cabeza, sucederán cosas malas.
Aunque las respuestas anteriores son lo suficientemente buenas, creo que es mucho más fácil pensar en términos de "copiar por valor".
Cuando pasa un puntero a una función, el valor de la dirección se copia al parámetro de la función. Debido al alcance de la función, esa copia desaparecerá una vez que regrese.
Al usar un puntero doble, podrá actualizar el valor del puntero original. El puntero doble aún se copiará por valor, pero eso no importa. Lo único que realmente importa es modificar el puntero original, evitando así el alcance o la pila de la función.
Espero que esto responda no solo a su pregunta, sino también a otras preguntas relacionadas con el puntero.
Como señaló en su respuesta , usando el puntero al puntero como un argumento en void push(struct node** head, int data) permite cambiar el puntero de la head directamente desde dentro de la función push lugar de devolver el nuevo puntero.
Hay otro buen ejemplo que muestra por qué el uso de puntero a puntero en lugar de un solo puntero puede acortar, simplificar y acelerar su código. Preguntaste acerca de agregar un nuevo nodo a la lista que probablemente no necesita puntero a puntero en contraste con eliminar el nodo de la lista de enlace único. Puede implementar la eliminación de un nodo de la lista sin puntero a puntero, pero no es óptimo. Describí los detalles here . También te recomiendo que veas este video de YouTube que aborda el problema.
Por cierto: si cuentas con la opinion Linus Torvalds , será mejor que aprendas a usar puntero a puntero. ;-)
Linus Torvalds: (...) En el extremo opuesto del espectro, realmente deseo que más personas entiendan el tipo de codificación de bajo nivel realmente central. No son cosas grandes y complejas como la búsqueda de nombres sin bloqueos, sino simplemente un buen uso de punteros a punteros, etc. Por ejemplo, he visto demasiadas personas que eliminan una entrada de lista enlazada de manera simple al realizar un seguimiento de la entrada "anterior" , y luego eliminar la entrada, haciendo algo como
if (prev) prev->next = entry->next; else list_head = entry->next;y cada vez que veo un código como ese, simplemente digo "Esta persona no entiende los punteros". Y es tristemente bastante común.
Las personas que entienden los punteros simplemente usan un "puntero al puntero de entrada" e inicializan eso con la dirección del list_head. Y luego, a medida que atraviesan la lista, pueden eliminar la entrada sin utilizar ninguna condición, simplemente haciendo un "* pp = entry-> next". (...)
Otros recursos que pueden ser útiles:
- C doble punteros
- Punteros a punteros
- ¿Por qué usar doble puntero? o ¿Por qué utilizar punteros a punteros?
Creo que el punto es que hace que sea más fácil actualizar los nodos dentro de una lista vinculada. Donde normalmente tendrías que hacer un seguimiento de un puntero para el anterior y el actual puedes tener un doble puntero para encargarse de todo.
#include <iostream>
#include <math.h>
using namespace std;
class LL
{
private:
struct node
{
int value;
node* next;
node(int v_) :value(v_), next(nullptr) {};
};
node* head;
public:
LL()
{
head = nullptr;
}
void print()
{
node* temp = head;
while (temp)
{
cout << temp->value << " ";
temp = temp->next;
}
}
void insert_sorted_order(int v_)
{
if (!head)
head = new node(v_);
else
{
node* insert = new node(v_);
node** temp = &head;
while ((*temp) && insert->value > (*temp)->value)
temp = &(*temp)->next;
insert->next = (*temp);
(*temp) = insert;
}
}
void remove(int v_)
{
node** temp = &head;
while ((*temp)->value != v_)
temp = &(*temp)->next;
node* d = (*temp);
(*temp) = (*temp)->next;
delete d;
}
void insertRear(int v_)//single pointer
{
if (!head)
head = new node(v_);
else
{
node* temp = new node(v_);
temp->next = head;
head = temp;
}
}
};
Cuando pasamos el puntero como parámetro en una función y queremos actualizar en el mismo puntero utilizamos el puntero doble.
Por otro lado, si pasamos el puntero como parámetro en una función y lo capturamos en un solo puntero, tendremos que devolver el resultado a la función de llamada para usar el resultado.
Digamos que anoté la dirección de tu casa en una tarjeta-1. Ahora si quiero decirle la dirección de su casa a otra persona, puedo copiar la dirección de la tarjeta-1 a la tarjeta-2 y dar la tarjeta-2 O puedo darle la tarjeta-1 directamente. De cualquier manera, la persona sabrá la dirección y podrá comunicarse con usted. Pero cuando doy la tarjeta-1 directamente, la dirección puede cambiarse en la tarjeta-1, pero si le doy la tarjeta-2, solo se puede cambiar la dirección en la tarjeta-2, pero no en la tarjeta-1.
Pasar un puntero a puntero es similar a dar acceso a la tarjeta-1 directamente. Pasar un puntero es similar a crear una nueva copia de la dirección.
En su ejemplo particular, no es necesario el doble puntero. Sin embargo, puede ser necesario si, por ejemplo, hicieras algo como esto:
struct node* push(struct node** head, int data)
{
struct node* newnode = malloc(sizeof(struct node));
newnode->data=data;
newnode->next=*head;
//vvvvvvvvvvvvvvvv
*head = newnode; //you say that now the new node is the head.
//^^^^^^^^^^^^^^^^
return newnode;
}
Imagina un caso en el que tienes que hacer ciertos cambios y esos cambios deberían reflejarse en la función de llamada.
Ejemplo:
void swap(int* a,int* b){
int tmp=*a;
*a=*b;
*b=tmp;
}
int main(void){
int a=10,b=20;
// To ascertain that changes made in swap reflect back here we pass the memory address
// instead of the copy of the values
swap(&a,&b);
}
De manera similar, pasamos la Dirección de Memoria del Jefe de la Lista.
De esta forma, si se agrega un nodo y se cambia el valor de la cabeza, ese cambio se refleja en la parte posterior y no es necesario reiniciar manualmente el cabezal dentro de la función de llamada.
Por lo tanto, este enfoque reduce las posibilidades de pérdida de memoria, ya que habríamos perdido el puntero al nodo recién asignado, si hubiéramos olvidado actualizar Head en la función de llamada.
Además de esto, el segundo código funcionará más rápido ya que no se desperdicia tiempo en copiar y devolver ya que trabajamos directamente con la memoria.
La forma estándar de manejar listas enlazadas en C es hacer que las funciones push y pop actualicen automáticamente el puntero de la cabeza.
C es "Llamar por valor", lo que significa que las copias de los parámetros se pasan a funciones. Si solo pasa el puntero de la cabeza, la persona que llama no verá ninguna actualización local que realice en ese puntero. Las dos soluciones son
1) Pase la dirección del puntero de la cabeza. (Puntero al puntero de la cabeza)
2) Regrese un nuevo puntero a la cabeza y confíe en la persona que llama para actualizar el puntero de la cabeza.
La opción 1) es la más fácil aunque un poco confusa al principio.
La respuesta es más obvia si se toma el tiempo de escribir una función de inserción de nodo de trabajo; el tuyo no es uno.
Necesita poder escribir sobre el encabezado para moverlo hacia adelante, por lo que necesita un puntero al puntero del encabezado para poder desreferenciarlo y llevar el puntero al encabezado y cambiarlo.
Piensa en la ubicación de la memoria para cabecera como [HEAD_DATA].
Ahora en su segundo escenario, la función main_head de la función de llamada es el puntero a esta ubicación.
main_head ---> [HEAD_DATA]
En su código, envió el valor del puntero main_head a la función (es decir, la dirección de la ubicación de memoria de head_data). Copió eso en local_head en la función. y ahora
local_head ---> [HEAD_DATA]
y
main_head ---> [HEAD_DATA]
Ambos apuntan a la misma ubicación, pero son esencialmente independientes entre sí. Entonces cuando escribas local_head = newnode; lo que hiciste es
local_head - / -> [HEAD_DATA]
local_head -----> [NEWNODE_DATA]
Simplemente reemplazó la dirección de memoria de la memoria anterior por una nueva en el puntero local. El main_head (puntero) aún apunta al antiguo [HEAD_DATA]
Tomemos esto simple, por ejemplo:
void my_func(int *p) {
// allocate space for an int
int *z = (int *) malloc(sizeof(int));
// assign a value
*z = 99;
printf("my_func - value of z: %d/n", *z);
printf("my_func - value of p: %p/n", p);
// change the value of the pointer p. Now it is not pointing to h anymore
p = z;
printf("my_func - make p point to z/n");
printf("my_func - addr of z %p/n", &*z);
printf("my_func - value of p %p/n", p);
printf("my_func - value of what p points to: %d/n", *p);
free(z);
}
int main(int argc, char *argv[])
{
// our var
int z = 10;
int *h = &z;
// print value of z
printf("main - value of z: %d/n", z);
// print address of val
printf("main - addr of z: %p/n", &z);
// print value of h.
printf("main - value of h: %p/n", h);
// print value of what h points to
printf("main - value of what h points to: %d/n", *h);
// change the value of var z by dereferencing h
*h = 22;
// print value of val
printf("main - value of z: %d/n", z);
// print value of what h points to
printf("main - value of what h points to: %d/n", *h);
my_func(h);
// print value of what h points to
printf("main - value of what h points to: %d/n", *h);
// print value of h
printf("main - value of h: %p/n", h);
return 0;
}
Salida:
main - value of z: 10
main - addr of z: 0x7ffccf75ca64
main - value of h: 0x7ffccf75ca64
main - value of what h points to: 10
main - value of z: 22
main - value of what h points to: 22
my_func - value of z: 99
my_func - value of p: 0x7ffccf75ca64
my_func - make p point to z
my_func - addr of z 0x1906420
my_func - value of p 0x1906420
my_func - value of what p points to: 99
main - value of what h points to: 22
main - value of h: 0x7ffccf75ca64
tenemos esta firma para my_func:
void my_func(int *p);
Si mira la salida, en fin, el valor que h señala es todavía 22 y el valor de h es el mismo, aunque en my_func se modificó. Cómo ?
Bueno, en my_func estamos manipulando el valor de p, que es solo un puntero local. después de llamar:
my_func(ht);
en main (), p mantendrá el valor que h contiene, que representa la dirección de la variable z, declarada en la función principal.
En my_func (), cuando estamos cambiando el valor de p para mantener el valor de z, que es un puntero a una ubicación en la memoria, para la cual hemos asignado espacio, no estamos cambiando el valor de h, que hemos pasado, pero solo el valor del puntero local p. Básicamente, p ya no tiene el valor de h, mantendrá la dirección de una ubicación de memoria a la que apunta z.
Ahora, si cambiamos nuestro ejemplo un poco:
#include <stdio.h>
#include <stdlib.h>
void my_func(int **p) {
// allocate space for an int
int *z = (int *) malloc(sizeof(int));
// assign a value
*z = 99;
printf("my_func - value of z: %d/n", *z);
printf("my_func - value of p: %p/n", p);
printf("my_func - value of h: %p/n", *p);
// change the value of the pointer p. Now it is not pointing to h anymore
*p = z;
printf("my_func - make p point to z/n");
printf("my_func - addr of z %p/n", &*z);
printf("my_func - value of p %p/n", p);
printf("my_func - value of h %p/n", *p);
printf("my_func - value of what p points to: %d/n", **p);
// we are not deallocating, because we want to keep the value in that
// memory location, in order for h to access it.
/* free(z); */
}
int main(int argc, char *argv[])
{
// our var
int z = 10;
int *h = &z;
// print value of z
printf("main - value of z: %d/n", z);
// print address of val
printf("main - addr of z: %p/n", &z);
// print value of h.
printf("main - value of h: %p/n", h);
// print value of what h points to
printf("main - value of what h points to: %d/n", *h);
// change the value of var z by dereferencing h
*h = 22;
// print value of val
printf("main - value of z: %d/n", z);
// print value of what h points to
printf("main - value of what h points to: %d/n", *h);
my_func(&h);
// print value of what h points to
printf("main - value of what h points to: %d/n", *h);
// print value of h
printf("main - value of h: %p/n", h);
free(h);
return 0;
}
tenemos la salida siguiente:
main - value of z: 10
main - addr of z: 0x7ffcb94fb1cc
main - value of h: 0x7ffcb94fb1cc
main - value of what h points to: 10
main - value of z: 22
main - value of what h points to: 22
my_func - value of z: 99
my_func - value of p: 0x7ffcb94fb1c0
my_func - value of h: 0x7ffcb94fb1cc
my_func - make p point to z
my_func - addr of z 0xc3b420
my_func - value of p 0x7ffcb94fb1c0
my_func - value of h 0xc3b420
my_func - value of what p points to: 99
main - value of what h points to: 99
main - value of h: 0xc3b420
Ahora, en realidad hemos cambiado el valor que h tiene, de my_func, al hacer esto:
- cambio de firma de función
- llamando desde main (): my_func (& h); Básicamente estamos pasando la dirección del puntero h al doble puntero p, declarado como un parámetro en la firma de la función.
- en my_func () lo estamos haciendo: * p = z; estamos desreferenciando el doble puntero p, un nivel. Básicamente esto se tradujo como lo harías: h = z;
El valor de p, ahora contiene la dirección del puntero h. El puntero h contiene la dirección de z.
Puedes tomar ambos ejemplos y diferenciarlos. Entonces, volviendo a tu pregunta, necesitas doble puntero para hacer modificaciones al puntero que has pasado directamente desde esa función.
Observación y hallazgo, POR QUÉ ...
Decidí hacer algunos experimentos y llegar a una conclusión,
OBSERVACIÓN 1- Si la lista vinculada no está vacía, entonces podemos agregar los nodos en ella (obviamente al final) usando solo un puntero.
int insert(struct LinkedList *root, int item){
struct LinkedList *temp = (struct LinkedList*)malloc(sizeof(struct LinkedList));
temp->data=item;
temp->next=NULL;
struct LinkedList *p = root;
while(p->next!=NULL){
p=p->next;
}
p->next=temp;
return 0;
}
int main(){
int m;
struct LinkedList *A=(struct LinkedList*)malloc(sizeof(struct LinkedList));
//now we want to add one element to the list so that the list becomes non-empty
A->data=5;
A->next=NULL;
cout<<"enter the element to be inserted/n"; cin>>m;
insert(A,m);
return 0;
}
Es simple de explicar (Básico). Tenemos un puntero en nuestra función principal que apunta al primer nodo (raíz) de la lista. En la función insert() pasamos la dirección del nodo raíz y usando esta dirección llegamos al final de la lista y le agregamos un nodo. Entonces podemos concluir que si tenemos la dirección de una variable en una función (no la función principal) podemos hacer cambios permanentes en el valor de esa variable de esa función que se reflejaría en la función principal.
OBSERVACIÓN 2- El método anterior de agregar nodo falló cuando la lista estaba vacía.
int insert(struct LinkedList *root, int item){
struct LinkedList *temp = (struct LinkedList*)malloc(sizeof(struct LinkedList));
temp->data=item;
temp->next=NULL;
struct LinkedList *p=root;
if(p==NULL){
p=temp;
}
else{
while(p->next!=NULL){
p=p->next;
}
p->next=temp;
}
return 0;
}
int main(){
int m;
struct LinkedList *A=NULL; //initialise the list to be empty
cout<<"enter the element to be inserted/n";
cin>>m;
insert(A,m);
return 0;
}
Si continúa agregando elementos y finalmente visualiza la lista, encontrará que la lista no ha sufrido cambios y aún está vacía. La pregunta que me llamó la atención fue en este caso, también estamos pasando la dirección del nodo raíz, por qué las modificaciones no están sucediendo como modificaciones permanentes y la lista en la función principal no sufre cambios. ¿POR QUÉ? ¿POR QUÉ? ¿POR QUÉ?
Luego observé una cosa, cuando escribo A=NULL la dirección de A convierte en 0. Esto significa que ahora A no está apuntando a ninguna ubicación en la memoria. Entonces eliminé la línea A=NULL; e hizo algunas modificaciones en la función de inserción.
algunas modificaciones, (a continuación, la función de insert() puede agregar solo un elemento a una lista vacía, solo escribió esta función para fines de prueba)
int insert(struct LinkedList *root, int item){
root= (struct LinkedList *)malloc(sizeof(struct LinkedList));
root->data=item;
root->next=NULL;
return 0;
}
int main(){
int m;
struct LinkedList *A;
cout<<"enter the element to be inserted/n";
cin>>m;
insert(A,m);
return 0;
}
el método anterior también falla porque en la función insert() raíz almacena la misma dirección que A en la función main() pero después de la línea root= (struct LinkedList *)malloc(sizeof(struct LinkedList)); la dirección almacenada en cambios de root . Por lo tanto, ahora, root (en la función insert() ) y A (en la función main() ) almacenan direcciones diferentes.
Entonces, el programa final correcto sería
int insert(struct LinkedList *root, int item){
root->data=item;
root->next=NULL;
return 0;
}
int main(){
int m;
struct LinkedList *A = (struct LinkedList *)malloc(sizeof(struct LinkedList));
cout<<"enter the element to be inserted/n";
cin>>m;
insert(A,m);
return 0;
}
Pero no queremos dos funciones diferentes para la inserción, una cuando la lista está vacía y otra cuando la lista no está vacía. Ahora viene el puntero doble que facilita las cosas.
Una cosa que noté que es importante es que los punteros almacenan la dirección y cuando se usan con ''*'' dan valor en esa dirección, pero los punteros tienen su propia dirección.
Ahora aquí está el programa completo y luego explica los conceptos.
int insert(struct LinkedList **root,int item){
if(*root==NULL){
(*root)=(struct LinkedList *)malloc(sizeof(struct LinkedList));
(*root)->data=item;
(*root)->next=NULL;
}
else{
struct LinkedList *temp=(struct LinkedList *)malloc(sizeof(struct LinkedList));
temp->data=item;
temp->next=NULL;
struct LinkedList *p;
p=*root;
while(p->next!=NULL){
p=p->next;
}
p->next=temp;
}
return 0;
}
int main(){
int n,m;
struct LinkedList *A=NULL;
cout<<"enter the no of elements to be inserted/n";
cin>>n;
while(n--){
cin>>m;
insert(&A,m);
}
display(A);
return 0;
}
siguientes son las observaciones,
1. la raíz almacena la dirección del puntero A (&A) , *root almacena la dirección almacenada por el puntero A y **root almacena el valor en la dirección almacenada por A En lenguaje simple root=&A , *root= A y **root= *A
2. si escribimos *root= 1528 significa que el valor en la dirección almacenada en la root convierte en 1528 y la dirección almacenada en la root es la dirección del puntero A (&A) ahora A=1528 (es decir, la dirección almacenada en A es 1528) y este cambio es permanente.
cada vez que estamos cambiando el valor de *root estamos cambiando el valor en la dirección almacenada en la root y desde root=&A (dirección del puntero A ) estamos cambiando indirectamente el valor de A o la dirección almacenada en A
entonces ahora si A=NULL (la lista está vacía) *root=NULL , así creamos el primer nodo y almacenamos su dirección en *root es decir, almacenamos indirectamente la dirección del primer nodo en A Si la lista no está vacía, todo es igual que en las funciones anteriores con un solo puntero, excepto que hemos cambiado la raíz a *root ya que lo que estaba almacenado en la raíz ahora está almacenado en *root .