Correct way to use malloc() and free with linked lists

Question

I am trying to understand malloc() better when it comes to linked list. Does this create memory for the pointer to the list as well as the fields inside of it? Such as:

  SomeStruct * someStructPtr = (SomeStruct *) malloc(sizeof(SomeStruct));

Alongside this, if I am trying to free this node AND the fields inside of it. Do I need to walk through all the fields (see code below). Does this just free the pointer (created from the line above) or does it free the pointer and and the fields.

free(someStructPtr);

For a more direct example. I have a struct of List and I'm trying to allocate space for this struct AND it's fields when it is created. I want to make sure I am creating, deleting, and using stdrup() correctly. My code is below:

Struct Declaration:

typedef struct ListNode_st
{
    char * str;
    struct ListNode_st * next;
} List;

Create Node:

List * List_createNode(const char * str){
  List * listPointer = (List *) malloc(sizeof(List));

  //make sure there was enough memory
  if(listPointer == NULL)
    return NULL;

  //malloc for next
  listPointer.next = (List *) malloc(sizeof(List *));
  if(listPointer.next == NULL)
    return NULL;
  listPointer.next = NULL;

  //malloc for str
  listPointer.str = strdup(str);
  //make sure enough space for the string to be copied
  if(listPointer.str == NULL)
    return NULL;

  //return value
  return listPointer;
}

Delete Node:

void List_destory(List * list){
  //base case -- (last item)
  if(list == NULL)
    return;
  //recurse case -- (there are more items)
  List_destroy(list->next);
  if(list->str != NULL)
    free(list->str);
  if(list->next != NULL)
    free(list->next);

  free(list);
}

Answer 1

Please don't cast the return value from malloc().

malloc(sizeof(SomeStruct))

allocates enough memory for one struct, and you then have to initialise every field within the struct.

calloc(1, sizeof(SomeStruct))

does the same but every byte of the struct is initialised to 0. malloc() and calloc() know nothing about your struct, they simply allocate the amount of memory you asked for. They return a void* pointer so that they can be used with any data type, about which they neither know nor care.

When you come to free() the allocated memory, the same applies - free() knows nothing about your struct, or even if it is a struct. It's up to you to free() any memory allocation within that struct, before you free() the memory for the struct. It does not free a struct. It frees the memory where the struct is.

So the answer is yes, you do need to walk through the whole data structure, otherwise any nested memory allocation pointers will be lost, resulting in memory leak.

Answer 2

List * List_createNode(const char * str){
  List * listPointer = (List *) malloc(sizeof(List));

  if(listPointer == NULL)
    return NULL;

  listPointer->next = NULL;

  listPointer->str = strdup(str);
  if(listPointer->str == NULL){
    free(listPointer);
    return NULL;
  }

  return listPointer;
}

void List_destory(List * list){
  if(list == NULL)
    return;
  List_destroy(list->next);
  free(list->str);
  free(list);
}

Answer 3

Let's warm up a little before we tackle your question.

int x = 42; 

Where does the memory of x come from? Is it allocated? Where? If this line is inside a function, the answer is: it is an "automatic" variable and the memory it uses is on the stack.

int * y = NULL;

Where does the memory for y come from now? There was no call to malloc() here and yet, y exists.

By now, you should be able to answer the first part of your question. malloc() is not allocating the memory for your pointer in this case.

struct Node
{
    struct Node * next;
    int value;
};

void InitNode( Node *node, int value )
{
    if(NULL != node)
    {
        node->next = NULL;
        node->value = value;
    }
}

// Not on HEAP, not on stack! Where? 
// This one gets its memory from "initvars" section.
int foo = 69; 

int main( int argc, const char * argv[] )
{
     struct Node n1; // instance located on stack...
     InitNode(&n1); // no malloc() to be seen... 

     // Instance located on HEAP, but n2, the pointer is located on stack,    
     // just like an int x = 42 would be.
     struct Node *n2 = malloc(sizeof(struct Node)); 
}

So, obviously in order to de-mystify what malloc() does requires to understand the different types of memory and how to deal with it.

So far we saw "automatic" aka "stack memory", we saw "initvars" memory. And we saw "heap" memory. malloc() is the function you use to allocate memory on the heap.

Last not least, there are yet other types of memory I will not mention here.

Answer 4

Does this create memory for the pointer to the list as well as the fields inside of it?

Given your struct type

typedef struct ListNode_st
{
    char * str;
    struct ListNode_st * next;
} List;

the following call will create memory for an instance of that struct:

List *l = malloc( sizeof *l ); // note no cast, operand of sizeof

l points to a block of memory large enough to contain two pointers; however, nothing's been allocated for either str or next to point to. You would have to allocate memory for the string and the next node separately:

l->str = malloc( N * sizeof *l->str ); // allocate N characters

or

l->str = strdup( str );

Note that in most linked list implementations, you don't allocate memory for next when you create a new node; that field is meant to point to another, previously allocated node in the list. You will set it when you insert a node following the current node.

Alongside this, if I am trying to free this node AND the fields inside of it. Do I need to walk through all the fields (see code below). Does this just free the pointer (created from the line above) or does it free the pointer and and the fields.

You need to free any allocated members first before deleting the entire node, such as

free( l->str );
free( l );

Freeing l does not free the memory that l->str points to.