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?

Ebarta

Are you having problems in unlinking the elements, or freeing them? If the latter, you call free() with the returned value from malloc(). – Tooley

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? – Ebarta

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. – Jermainejerman

@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. – Majors

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. – Ebarta

@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. – Majors

@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. – Majors

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. – Ebarta

Answer 1

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:

1. check if head is NULL, if yes the list is empty and we just return

2. 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

3. Now we can safely free(tmp) variable, and head just points to the rest of the list, go back to step 1

Majors

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. – Stilly

@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); – Awildaawkward

@Robert yes exactly! If you free'd tmp first then tmp->data would probably point to garbage and you will get a seg fault. – Majors

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. – Statocyst

You all are ignoring that a non NULL head pointer will not break the loop at all. – An

Answer 2

Simply by iterating over the list:

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

Abaxial

Answer 3

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;
    }

}

Rusert

Answer 4

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("->");
    }
}

Lukasz

Answer 5

You could always do it recursively like so:

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

Reticular

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. – Abaxial

@Abaxial 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. – Reticular

this would be ok in languages that can do tail recursion. and that's not C – Colure

This code is not tail recursive. (It s doing something after the recursion) And cannot benefit from tail recursion optimization – Sherasherar

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? – Implausibility

Answer 6

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);
    }

Undoing

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. – Belldame