Answer.
Dynamic data structures in C (e.g., linked lists, trees) are usually implemented manually using pointers and dynamic memory allocation (malloc, calloc, free).
Key nuances in implementation:
- Always initialize pointers: garbage in uninitialized pointers leads to leaks or segmentation faults.
- Handle memory allocation errors: check the result of malloc/calloc, otherwise the program may work with an invalid pointer.
- Properly free memory: do not forget to call free for each allocated structure to avoid memory leaks.
- Avoid dangling pointers (nullify the pointer after free).
Example: creating and freeing a simple singly linked list
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);
}
}
Trick question.
Is it correct to free the memory of the list nodes within the loop using only the current pointer?
It is incorrect to free the current node without first saving the next one! After calling free, the memory at the address may be overwritten or returned to the OS.
Correct approach:
Node* curr = head;
while (curr) {
Node* next = curr->next;
free(curr);
curr = next;
}
If you do not save next, it results in accessing already freed (and potentially not yours!) memory.
History
Due to forgetting to free the entire list (free) on error termination of one of the operations, an autotest working on 10,000 addition/deletion operations gradually increased memory consumption - the profiler showed a significant leak.
The developer kept a pointer to the last node of the list but did not nullify it after deleting all elements, which caused a difficult-to-trace segfault in another function that referenced already freed memory.
When working with trees, they forgot to recursively delete all "subtrees," freeing only the root node. The result: due to incomplete cleaning, the memory structure remained dirty, leading to periodic crashes.