Réponse.
Les structures de données dynamiques en C (par exemple, les listes liées, les arbres) sont généralement implémentées manuellement à l'aide de pointeurs et d'allocation dynamique de mémoire (malloc, calloc, free).
Nuances clés lors de l'implémentation :
- Initialisez toujours les pointeurs : des déchets dans les pointeurs non initialisés entraînent des fuites de mémoire ou des segfaults.
- Gérez les erreurs d'allocation de mémoire : vérifiez le résultat de malloc/calloc, sinon le programme peut fonctionner avec un pointeur invalide.
- Libérez correctement la mémoire : n'oubliez pas d'appeler free pour chaque structure allouée afin d'éviter l'accumulation de fuites.
- Évitez les pointeurs pendants (mettez le pointeur à null après free).
Exemple : création et suppression d'une simple liste chaînée
typedef struct Node {
int value;
struct Node* next;
} Node;
Node* create_node(int value) {
Node* n = malloc(sizeof(Node));
if (!n) return NULL;
n->value = value;
n->next = NULL;
return n;
}
void free_list(Node* head) {
while (head) {
Node* tmp = head;
head = head->next;
free(tmp);
}
}
Question piège.
Peut-on libérer la mémoire des nœuds de la liste à l'intérieur de la boucle en utilisant seulement le pointeur courant ?
Il est incorrect de libérer le nœud actuel sans avoir d'abord sauvegardé le suivant ! Après l'appel à free, la mémoire à cette adresse peut être réécrite ou retournée par le système d'exploitation.
Approche correcte :
Node* curr = head;
while (curr) {
Node* next = curr->next;
free(curr);
curr = next;
}
Si vous ne sauvegardez pas next, vous risquez d'accéder à une mémoire déjà libérée (et potentiellement pas la vôtre !).
Histoire
En raison de l'oubli de nettoyer toute la liste (free) lors d'une mauvaise terminaison d'une des opérations, un test automatique fonctionnait avec 10000 opérations d'ajout/suppression, ce qui a progressivement augmenté la consommation de mémoire - le profileur a montré une grande fuite.
Le développeur conservait un pointeur sur le dernier nœud de la liste, mais ne le mettait pas à null après avoir supprimé tous les éléments, ce qui a conduit, dans une autre fonction, à référencer de la mémoire déjà libérée, provoquant un segfault difficile à tracer.
Lors de la manipulation d'arbres, on a oublié de supprimer récursivement tous les "sous-arbres", en ne libérant que le nœud racine. En résumé : en raison d'un nettoyage incomplet, la structure de mémoire restait sale, entraînant des plantages intermittents.