Odpowiedź.
Dynamiczne struktury danych w C (np. listy powiązane, drzewa) są zazwyczaj implementowane ręcznie przy użyciu wskaźników i dynamicznego przydzielania pamięci (malloc, calloc, free).
Kluczowe niuanse przy implementacji:
- Zawsze inicjalizuj wskaźniki: śmieci w nieinicjalizowanych wskaźnikach prowadzą do wycieków lub błędów segmentacji.
- Obsługuj błędy przydzielania pamięci: sprawdzaj wynik malloc/calloc, w przeciwnym razie program może działać z nieprawidłowym wskaźnikiem.
- Poprawnie zwalniaj pamięć: nie zapomnij wywołać free dla każdej alokowanej struktury, aby uniknąć akumulacji wycieków.
- Unikaj wiszących wskaźników (po free zera wskaźnik).
Przykład: tworzenie i usuwanie prostego jednokierunkowego listy
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);
}
}
Pytanie podchwytliwe.
Czy można zwalniać pamięć węzłów listy wewnątrz pętli, używając tylko bieżącego wskaźnika?
Niepoprawnie jest zwalniać bieżący węzeł bez wcześniejszego zapisania następnego! Po wywołaniu free pamięć pod adresem może być nadpisana lub zwrócona systemowi operacyjnemu.
Poprawne podejście:
Node* curr = head;
while (curr) {
Node* next = curr->next;
free(curr);
curr = next;
}
Jeśli nie zapiszesz next — dochodzi do odwołania do już zwolnionej (i potencjalnie nie twojej!) pamięci.
Historia
Z powodu zapomnienia o oczyszczeniu całej listy (free) przy błędnym zakończeniu jednej z operacji test automatyczny na 10000 operacjach dodawania/usuwania działał, co powodowało stopniowy wzrost zużycia pamięci — profiler pokazał dużą stratę pamięci.
Programista przechowywał wskaźnik na ostatni węzeł listy, ale nie zerał go po usunięciu wszystkich elementów, co spowodowało, że w innej funkcji, odwołując się do już zwolnionej pamięci, otrzymał trudny do uchwycenia błąd segfault.
Podczas pracy z drzewami zapomniano rekurencyjnie usunąć wszystkie "poddrzewa", zwalniając tylko węzeł korzeniowy. W efekcie: z powodu niepełnego oczyszczenia struktura pamięci pozostawała brudna, prowadząc do okresowych awarii.