Respuesta.
Las estructuras de datos dinámicas en C (por ejemplo, listas enlazadas, árboles) suelen implementarse manualmente utilizando punteros y asignación de memoria dinámica (malloc, calloc, free).
Matices clave en la implementación:
- Siempre inicialice los punteros: la basura en punteros no inicializados lleva a fugas de memoria o fallos de segmentación.
- Maneje los errores de asignación de memoria: verifique el resultado de malloc/calloc, de lo contrario, el programa puede trabajar con un puntero no válido.
- Liberar memoria correctamente: no olvide llamar a free para cada estructura asignada, para evitar acumulación de fugas.
- Evite punteros colgantes (después de free, anule el puntero).
Ejemplo: creación y eliminación de una lista enlazada simple
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);
}
}
Pregunta capciosa.
¿Es posible liberar la memoria de los nodos de la lista dentro del ciclo usando solo el puntero actual?
No es correcto liberar el nodo actual sin guardar previamente el siguiente. ¡Después de llamar a free, la memoria en esa dirección puede ser sobrescrita o devuelta al sistema operativo!
Enfoque correcto:
Node* curr = head;
while (curr) {
Node* next = curr->next;
free(curr);
curr = next;
}
Si no se guarda next, se produce un acceso a la memoria ya liberada (¡y potencialmente no suya!).
Historia
Debido a olvidar limpiar toda la lista (free) al finalizar incorrectamente una de las operaciones, un test automático funcionaba con 10000 operaciones de adición/eliminación, lo que provocó un aumento gradual en el consumo de memoria — el perfilador mostró una gran fuga.
El desarrollador mantenía un puntero al último nodo de la lista, pero no lo anuló después de eliminar todos los elementos, lo que provocó, en otra función, un acceso a memoria ya liberada y un difícil de rastrear segfault.
Al trabajar con árboles, olvidamos eliminar recursivamente todos los "subárboles", liberando solo el nodo raíz. Resultado: debido a la limpieza incompleta, la estructura de memoria permaneció sucia, causando fallos periódicos.