C: How to free nodes in the linked list?

Question

How will I free the nodes allocated in another function?

struct node {
    int data;
    struct node* next;
};

struct node* buildList()
{
    struct node* head = NULL;
    struct node* second = NULL;
    struct node* third = NULL;

    head = malloc(sizeof(struct node));
    second = malloc(sizeof(struct node));
    third = malloc(sizeof(struct node));

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    return head;
}

I call the buildList function in the main()

int main()
{
    struct node* h = buildList();
    printf("The second element is %d\n", h->next->data);
    return 0;
}

I want to free head, second and third variables.
Thanks.

Update:

int main()
{
    struct node* h = buildList();
    printf("The element is %d\n", h->next->data);  //prints 2
    //free(h->next->next);
    //free(h->next);
    free(h);

   // struct node* h1 = buildList();
    printf("The element is %d\n", h->next->data);  //print 2 ?? why?
    return 0;
}

Both prints 2. Shouldn't calling free(h) remove h. If so why is that h->next->data available, if h is free. Ofcourse the 'second' node is not freed. But since head is removed, it should be able to reference the next element. What's the mistake here?

Are you having problems in unlinking the elements, or freeing them? If the latter, you call `free()` with the returned value from `malloc()`. — vhallac, Jun 20 '11 at 20:38
user349433: This isn't HW, I tried with free(h) in main. Then if h is not there then how come h->next->data gives the value 2? So I asked. But free(h->next) should also be called. But then since h is the head, and after removing the head, I must not be able to reference head->next, isn't it. Where did I make mistake? — , Jun 20 '11 at 20:48
```free()``` does not erase the content of the memory, it merely allows those contents to be reused later. The pointer ```h->next``` remains valid as a coincidence because the memory you ```free()```'d has not yet been reused. — Heath Hunnicutt, Jun 20 '11 at 20:53
@jase21 you should first `free` the last node on your list, because if you free for example `h` then you won't be able to get `h->next` because `h` won't exist, except if you use a temporary variable to hold `h->next` and then `free` `h`. If you just wan to `free` these 3 nodes you could do: `free(h->next->next)` which will `free` the `third` node, then `free(h->next)` which will `free` `second` node, and then `free(h)` which will `free` the `head` node. But you CANNOT `free(h)` first because then you won't be able to do `free(h->next)` for the rest of your list nodes. — insumity, Jun 20 '11 at 20:55
Luzhin: Yes, that's what I thought. But please see the updated main(). I ran it and somehow our theory doesn't seems to work. Like Heath Hunnicutt said, may be it still exists. But I still don't understand why. — , Jun 20 '11 at 20:59
@jase21 Well Heath answered to this. It just works when you tried it, but it's not guaranteed that it will work in the future or by another machine. In another machine doing `h->next->data` could get you a segmentation fault. Ok, let's say you have `h` having the following data: `h->next = 0x12341281; h->data = 1`, when you do `free(h)` you just let know the machine that in a future `malloc` you can overwrite `h`, that `h` is not more used by your program. But the data `h->next = 0x12341281; h->data = 1` seem to keep existing, that doesn't mean you should use them. — insumity, Jun 20 '11 at 21:07
@jase21 Maybe in a future `malloc`, where `h->next` and `h->data` is saved, something else will be written. And then when doing `h->next->data` will get you a segmentation fault. — insumity, Jun 20 '11 at 21:10
Yes, now I get it. So that's the reason why programmers often tell to assign a NULL after calling free() just in case.. Thanks all. — , Jun 20 '11 at 21:16

score 113 · Accepted Answer · answered Jun 20 '11 at 20:36

113

An iterative function to free your list:

void freeList(struct node* head)
{
   struct node* tmp;

   while (head != NULL)
    {
       tmp = head;
       head = head->next;
       free(tmp);
    }

}

What the function is doing is the follow:

check if head is NULL, if yes the list is empty and we just return
Save the head in a tmp variable, and make head point to the next node on your list (this is done in head = head->next
Now we can safely free(tmp) variable, and head just points to the rest of the list, go back to step 1

answered Jun 20 '11 at 20:36

insumity

5,311
8
36
64

2

Just be sure the set the list head pointer to null after passing it to this function. In fact, it's a good idea to set each next pointer of each node to null before freeing the node, too. – David R Tribble Jun 20 '11 at 20:38
4

@foobar If the data in the node was created using malloc too, would we have to free that BEFORE we freed temp? Like: free(tmp->data); free(tmp); – Robert Cardona Mar 14 '13 at 06:47
5

@Robert yes exactly! If you free'd `tmp` first then tmp->data would probably point to garbage and you will get a seg fault. – insumity Mar 14 '13 at 20:30
Perhaps it would be better to pass the head pointer by reference and NULL the pointer directly in the FreeList function. So, it would be void freeList(struct node** head){blah; blah; *head = NULL;}. This would avoid the problem that David mentions. – m_a_s Jan 06 '17 at 12:33
You all are ignoring that a non NULL head pointer will not break the loop at all. – Dario Rodriguez Jul 09 '18 at 19:35

score 6 · Answer 2 · edited Oct 02 '13 at 15:04

6

Simply by iterating over the list:

struct node *n = head;
while(n){
   struct node *n1 = n;
   n = n->next;
   free(n1);
}

edited Oct 02 '13 at 15:04

Jared Burrows

54,294
25
151
185

answered Jun 20 '11 at 20:37

elcuco

8,948
9
47
69

score 2 · Answer 3 · answered Jan 29 '18 at 06:12

2

One function can do the job,

void free_list(node *pHead)
{
    node *pNode = pHead, *pNext;

    while (NULL != pNode)
    {
        pNext = pNode->next;
        free(pNode);
        pNode = pNext;
    }

}

answered Jan 29 '18 at 06:12

Mehul

43
1
6

score 2 · Answer 4 · edited May 15 '20 at 12:03

2

struct node{
    int position;
    char name[30];
    struct node * next;
};

void free_list(node * list){
    node* next_node;

    printf("\n\n Freeing List: \n");
    while(list != NULL)
    {
        next_node = list->next;
        printf("clear mem for: %s",list->name);
        free(list);
        list = next_node;
        printf("->");
    }
}

edited May 15 '20 at 12:03

wilkben

657
3
12

answered May 14 '20 at 22:16

Manolis

21
1

score 1 · Answer 5 · answered Jun 20 '11 at 20:37

1

You could always do it recursively like so:

void freeList(struct node* currentNode)
{
    if(currentNode->next) freeList(currentNode->next);
    free(currentNode);
}

answered Jun 20 '11 at 20:37

Bradley Swain

804
5
12

3

argg, recursion is nice on paper... but in reality it's memory and CPU demands is very costy compared to simple loops like I or jase21 did. Unwinding the stack is not cheap when you have 1328786 nodes. – elcuco Jun 20 '11 at 20:40
1

@elcuco I agree actually. In a case like the one the question presents, it'll perform fine, but if you're looking at lists that large, there's no question a loop is going to put you in a better position. – Bradley Swain Jun 20 '11 at 21:02
this would be ok in languages that can do tail recursion. and that's not C – Tomáš Nesrovnal Dec 09 '15 at 08:13
This code is *not* tail recursive. (It s doing something after the recursion) And cannot benefit from tail recursion optimization – HAL9000 Jul 04 '19 at 12:01
1

I think this function would cause an error if called on a node that is NULL. Maybe put a NULL check in the first line of the definition instead of checking if the next node is null? – Brent Pappas Jan 24 '21 at 23:02

score 0 · Answer 6 · answered Jul 02 '23 at 18:29

0

int delf(Node **head)
{
    if(*head==NULL)
    {
        printf("Empty\n");
        return 0;
    }
    else
    {
        Node *temp=*head;
        *head=temp->next;
        free(temp);
    }
    return 0;
}
 while(head!=NULL)
    {
        delf(&head);
    }

answered Jul 02 '23 at 18:29

35 AK AMOGH.KULKARNI

1

Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Jul 04 '23 at 12:13

C: How to free nodes in the linked list?

6 Answers6

Linked