Stack Exchange
Confusion in Free'ing a linked list structure in C
I am juggling with two ways of free()'ing malloc()'ed memory in a linked list structure. Suppose I create a singly linked list with the following C code;
#include<stdio.h>
#include<stdlib.h>

struct node_type{
  int data;
  struct node_type *next;
  struct node_type *prev;
}
typedef struct node_type node; 
typedef struct node_type *list; 

void main(void){
  list head,node1,tail;
  head=(list)malloc(sizeof(node));
  tail=(list)malloc(sizeof(node));
  node1=(list)malloc(sizeof(node));
  head->next=node1;tail->prev=node1;
  node1->prev=head;node1->next=tail;node1->data=1;

  /*Method-1 for memory de-allocation*/
  free(head->next->next);
  free(head->next);
  free(head);

  /*OR*/

  /*Method-2 for memory de-allocation*/
  free(tail);
  free(node1);
  free(head);

  /*OR*/

  /*Method-3 for memory de-allocation*/
  free(node1);
  free(tail);
  free(head); 
}

Now, I have the following questions:
Q1) Which of the three methods of memory de-allocation shown in code above are correct/incorrect.
Q2) Is is necessary to follow any order in the free()'ing memory as used in Methods 1 and 2 for memory de-allocation OR randomly free()'ing memory is also fine?

These only work if you have 3 nodes... You probably want some kind of loop to do this no?

And do not for the name of Jesus cast the damn return value of poor malloc()!

@Caleb No, it isn't. I am new to C and data structures. I was trying to implement the linked list DS, but was unsure of usage of free. Hence the question.

@Justin Yes, I would do that later. One thing at a time. I didnt want to create a long list, play with it without being sure of the way to free the allocated memory.

@H2CO3 +1 for pointing out NOOB bad practice/mistake.

Thanks. I used to read the Kernel Coding Guidelines. :P

All the methods you showed are correct, you should follow a specific order only when the pointer to an allocated memory exists only in another allocated memory, and you will lose it if you free the container first.
For example, for the allocation:
int ** ipp;
ipp = malloc(sizeof(int*));
*ipp = malloc(sizeof(int));

The correct free order will be:
free(*ipp);
free(ipp);

and not:
free(ipp);
free(*ipp); // *ipp is already invalid


You could free them the other way around if you wanted, but you would have to save ipp to a temporary variable first. The issue is not that the order is important to malloc/free, but that if you free your last reference to a memory block, you can no longer refer to it.

@DavidHeffernan - Sure, That's why I said if it exists only in the container.

All of these methods work fine. You can free memory blocks allocated by malloc in whatever order you like.
Just imagine for a moment that the order in which you allocated memory had to be reversed when you freed it. If that was so you could never insert or delete items from the middle of a list. Your only available dynamically allocated data structure would be a push-down stack.

Here's a simple way to free a linked list, starting at the head. (Note, this assumes "next" will be NULL if you're at the end of the list.)
node * it = head;
while( NULL != it ) {
  node * tmp = it;
  it = it->next;
  free(tmp);
}


Thanks for the reply but I only required to know method of freeing the linked-list and significance of the order of freeing. Although, your reply is my next step in learning to use linked lists.
