¿Cuál es el motivo para utilizar un puntero doble al agregar un nodo en una lista vinculada?
Los dos ejemplos de código siguientes agregan un nodo en la parte superior de una lista vinculada. Pero mientras que el primer ejemplo de código usa un puntero doble, el segundo ejemplo de código usa un puntero único.
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 utilizan una lista enlazada utilizan un puntero doble para agregar un nuevo nodo. Sé lo que es un doble puntero. Pero si un solo puntero fuera suficiente para agregar un nuevo nodo, ¿por qué muchas implementaciones dependen de punteros dobles?
¿Hay algún caso en el que un solo puntero no funcione, por lo que debemos optar por un puntero doble?
Algunas implementaciones pasan un parámetro de puntero a puntero para permitir cambiar el puntero principal directamente en lugar de devolver el nuevo. Así 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 principal debe devolver el nuevo encabezado, y la persona que llama es responsable de actualizarlo él mismo:
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, perderá los nodos que asigne con malloc y el puntero principal siempre apuntará al mismo nodo.
La ventaja debería quedar clara ahora: con el segundo, si la persona que llama se olvida de asignar el nodo devuelto al puntero principal, sucederán cosas malas.
Editar:
Puntero a puntero (punteros dobles) también permite la creación de múltiples tipos de datos definidos por el usuario dentro de un mismo programa (Ejemplo: creación de 2 listas vinculadas)
Para evitar la complejidad de los punteros dobles, siempre podemos utilizar la estructura (que funciona como un puntero interno).
Puede definir una lista de la siguiente manera:
typedef struct list {
struct node* root;
} List;
List* create() {
List* templ = malloc(sizeof(List));
templ->root = NULL;
return templ;
}
En las funciones de lista de enlaces, utilice la Lista anterior de la siguiente manera: (Ejemplo de función Push)
void Push(List* l, int x) {
struct node* n = malloc(sizeof(struct node));
n->data = x;
n->link = NULL;
printf("Node created with value %d\n", n->data);
if (l->root == NULL) {
l->root = n;
} else {
struct node* i = l->root;
while (i->link != NULL){
i = i->link;
}
i->link = n;
}
}
En su función main() declare la lista de la siguiente manera:
List* list1 = create();
push(list1, 10);
Aunque las respuestas anteriores son bastante 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 utilizar un puntero doble, podrá actualizar el valor del puntero original. El doble puntero se seguirá copiando por valor, pero eso no importa. Lo único que realmente te 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 sugerencias.
Como @R. Martinho Fernandes señaló en su respuesta que el uso de puntero a puntero como argumento void push(struct node** head, int data)le permite cambiar el headpuntero directamente desde la pushfunción en lugar de devolver el nuevo puntero.
Hay otro buen ejemplo que muestra por qué el uso de puntero a puntero en lugar de un único puntero puede acortar, simplificar y acelerar el código. Usted preguntó acerca de agregar un nuevo nodo a la lista que probablemente normalmente no necesita puntero a puntero en contraste con eliminar el nodo de la lista enlazada individualmente. Puede implementar la eliminación de nodos de la lista sin puntero a puntero, pero no es óptimo. Describí los detalles aquí . Te recomiendo también que veas este video de YouTube que aborda el problema.
Por cierto: si cuentas con la opinión de Linus Torvalds , será mejor que aprendas a usar puntero a puntero. ;-)
Linus Torvalds: (...) En el extremo opuesto del espectro, realmente desearía que más personas entendieran el tipo de codificación de bajo nivel realmente fundamental. No son cosas grandes y complejas como la búsqueda de nombres sin bloqueo, sino simplemente un buen uso de punteros a punteros, etc. Por ejemplo, he visto a demasiadas personas que eliminan una entrada de lista con un solo enlace manteniendo un registro 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 consejos". Y lamentablemente es bastante común.
Las personas que entienden los punteros simplemente usan un "puntero al puntero de entrada" y lo inicializan con la dirección de list_head. Y luego, a medida que recorren la lista, pueden eliminar la entrada sin utilizar ningún condicional, simplemente haciendo "*pp = entrada->siguiente". (...)
Otros recursos que pueden ser útiles:
- C punteros dobles
- Punteros a punteros
- ¿Por qué utilizar doble puntero? o ¿Por qué utilizar punteros a punteros?
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;
}
