Freeing an entire linked list in C

Question

I know this question has been asked a lot on this site so I apologize for asking it again but I'm really stuck. I'm trying to create a function that deletes an entire linked list (in C). Any advice would really help me. I attached my current code for the function, the linked list structure, and the results on Valgrind.

typedef struct node { void* data; struct node* next; } node_t; typedef struct list { node_t* head; int (*comparator)(void*, void*); void (*printer)(void*); void (*deleter)(void*); int length; } list_t; void DestroyList(list_t* list) { if (list == NULL) return; struct list_t* curr; while (list != NULL) { curr = list; list = list->head->next; free(curr); } }

Valgrind output:

[[ Valgrind Errors Detected ]] ==1045== Memcheck, a memory error detector ==1045== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==1045== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info ==1045== Command: ./main ==1045== Parent PID: 16 ==1045== ==1045== Use of uninitialised value of size 8 ==1045== at 0x109DDC: DestroyList (hw2.c:123) ==1045== by 0x10964F: _genos_unittest (DestroyList_small_list.c:30) ==1045== by 0x109517: main (genos_unittest.h:173) ==1045== ==1045== Invalid read of size 8 ==1045== at 0x109DDC: DestroyList (hw2.c:123) ==1045== by 0x10964F: _genos_unittest (DestroyList_small_list.c:30) ==1045== by 0x109517: main (genos_unittest.h:173) ==1045== Address 0x2e2e2e35 is not stack'd, malloc'd or (recently) free'd ==1045== ==1045== ==1045== HEAP SUMMARY: ==1045== in use at exit: 95 bytes in 8 blocks ==1045== total heap usage: 10 allocs, 2 frees, 151 bytes allocated ==1045== ==1045== 16 bytes in 1 blocks are definitely lost in loss record 6 of 8 ==1045== at 0x4C31B0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==1045== by 0x1095B0: _genos_unittest (DestroyList_small_list.c:17) ==1045== by 0x109517: main (genos_unittest.h:173) ==1045== ==1045== 16 bytes in 1 blocks are definitely lost in loss record 7 of 8 ==1045== at 0x4C31B0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==1045== by 0x10975A: InsertAtHead (linkedlist.c:54) ==1045== by 0x109643: _genos_unittest (DestroyList_small_list.c:27) ==1045== by 0x109517: main (genos_unittest.h:173) ==1045== ==1045== 37 (16 direct, 21 indirect) bytes in 1 blocks are definitely lost in loss record 8 of 8 ==1045== at 0x4C31B0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==1045== by 0x10975A: InsertAtHead (linkedlist.c:54) ==1045== by 0x1095A6: _genos_unittest (DestroyList_small_list.c:15) ==1045== by 0x109517: main (genos_unittest.h:173) ==1045== ==1045== LEAK SUMMARY: ==1045== definitely lost: 48 bytes in 3 blocks ==1045== indirectly lost: 21 bytes in 2 blocks ==1045== possibly lost: 0 bytes in 0 blocks ==1045== still reachable: 26 bytes in 3 blocks ==1045== suppressed: 0 bytes in 0 blocks ==1045== Reachable blocks (those to which a pointer was found) are not shown. ==1045== To see them, rerun with: --leak-check=full --show-leak-kinds=all ==1045== ==1045== For counts of detected and suppressed errors, rerun with: -v ==1045== Use --track-origins=yes to see where uninitialised values come from ==1045== ERROR SUMMARY: 5 errors from 5 contexts (suppressed: 0 from 0)

Again, any help would really be appreciated. Thank you!

MikeCAT · Accepted Answer · 2021-04-12 20:57:59Z

3

list has type list_t*, but list->head->next has type struct node*. You should use a pointer with proper type to traverse the list.

It will be like this:

void DestroyList(list_t* list) { if (list == NULL) return; node_t* itr = list->head; node_t* curr; while (itr != NULL) { curr = itr; itr = itr->next; // if appropriate // free(curr->data); free(curr); } // if appropriate // free(list); }

answered Apr 12, 2021 at 20:57

MikeCAT

75.1k11 gold badges50 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

David C. Rankin Over a year ago

Types don't matter do they? :) Good additional comments.

John Walling Over a year ago

Thank you so much for your help. However, Valgrind is still 3 memory leaks for some reason. Do you think I need to free the comparator, printer, and deleter?

MikeCAT Over a year ago

No. Functions will usually statically allocated in memory and won't be needed to be freed. This is "usually" and functions can also be stored on dynamically allocated memory, so I cannot definitely say about that without seeing what is assigned there.

David C. Rankin Over a year ago

@JohnWalling Make sure you close any files you open or valgrind will show that as an allocation that isn't freed.

Remy Lebeau · Accepted Answer · 2021-04-12 20:59:15Z

Your DestroyList() is implemented wrong (it should not even compile, as you are trying to assign a struct node* pointer to a list_t* pointer).

Try this instead:

void DestroyList(list_t* list) { if (list == NULL) return; struct list_t *curr = list->head, *next; while (curr != NULL) { next = curr->next; free(curr); curr = next; } // depending on whether you want the list to be just cleared, // or actually destroyed, you need either: list->head = NULL; // or: free(list); }

Vlad from Moscow · Accepted Answer · 2021-04-12 21:26:34Z

For starters it is unclear whether the data member data of the structure struct node points to a dynamically allocated object.

typedef struct node { void* data; struct node* next; } node_t;

In general it should point to a dynamically allocated object.

Secondly an object of the type struct list can have automatic storage duration. So within the function DestroyList the pointer list shall not be used to free the pointed object of the type struct list.

Within the function you need to free all dynamically allocated nodes and other objects pointed to by the data member data.

After calling the function the list shall be a valid empty list.

And each list has only one object of the type struct list. So for example these lines

struct list_t* curr; //... curr = list; //... free(curr);

do not make a sense.

So the function can be defined the following way

void DestroyList( list_t *list ) { while ( list->head != NULL ) { node_t *curr = list->head; list->head = list->head->next; free( curr->data ); free( curr ); } list->length = 0; }

Collectives™ on Stack Overflow

Freeing an entire linked list in C

3 Answers 3

4 Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

Comments

Related