C/Pointeur de pointeur

Un article de Le wiki de 2 noisettes - noisette.ch.

Les pointeurs de pointeurs, c'est comme le h de hawai, ça sert à rien.

Un petit exemple de leur utilisation :

Une petite structure qui s'apparente à une liste chainée et un pointeur sur le premier élément :

struct dummy_struct {
  long value;
  dummy_struct * next;
}
dummy_struct * first;

Si on veut insérer la structure new_s au milieu de la chaine (par exemple pour trier value par ordre croissant), on fait une boucle qui parcourt les stuctures jusqu'à ce qu'on trouve celle dont la valeur est plus grande que la nouvelle valeur à insérer :

for (dummy_struct* s = first; s != NULL; s = s->next) {
  if (s->value > new_s->value) break;
}

s pointe donc sur l'élément suivant, donc natuellement

new_s->next = s;

Mais en il nous faut encore lier la stucture précédente à new_s pour compléter l'insertion. On peut avoir un deuxième pointeur dummy_struct* previous_s qu'on met à jour à chaque itération de la boucle :

for (dummy_struct* s = first; s != NULL; s = s->next) {
  if (s->value > new_s->value) break;
  previous_s = s;
}

Ou alors on peut passer par un pointeur de pointeur :

dummy_struct **s;
for (s = &first; *s != NULL; s = *(&s)->next) {
  if ((*s)->value > new_s->value) break;
}

Une fois la boucle terminée, s pointe sur le lien qu'on voulait changer précédemment. Il nous reste donc à écrire à cette adresse pour que le tour soit joué.

new_s->next = *s;
*s = new_s;

Le résultat est complètement équivalent, mais la seconde solution est bien plus efficace en terme de temps d'exécution (moitié moins d'écriture mémoire) et utilise une variable de moins.