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

Solution 1

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

Solution 2

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.

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

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

View more solutions

Comments

[Jason Hu]

what you did is correct(at least no obvious error), but your idea is a little bit biased. malloc allocates a block of memory for you, only. it doesn't know and doesn't care about the fields inside. and yes, free only frees one layer only so you need to free the fields inside if necessary.

[Jason Hu]

but there is a regular arguable issue: stackoverflow.com/questions/605845/… .

[napkinsterror]

I usually don't cast in C, unless I am unsure about what I am doing, but now I definitely won't thanks!

[BitTickler]

The don't cast in C always comes up. And always a link to that idiomatic question. My corollary to that is (as usual): Don't cast in C IFFFFFFF you are sure you that code will only be compiled by a C-compiler for the next 500 years.

[napkinsterror]

This seems great. I'm guessing by your answer that setting the fields (like listPointer->next = NULL) is doing enough and that I don't need to malloc it. Secondly, I need to be sure to destroy the str field inside of the list as well. I was pretty much asking, if what your free() statement destroys the list->str as well as destroying the list pointer.

[napkinsterror]

Thanks! I only wish you would have done it more like my example, but I get it. I have a great understanding of stacks, heaps, and low level computer hardware, but I just wanted to know why or why not to malloc the fields inside of the node after it has been malloc'ed. (Especially for the next field as it would require me to malloc another struct).

[BitTickler]

It all depends on what you are planning on doing. Having each node allocated individually on the heap does not help with "locality". So, while many schoolbooks do exactly that, you might as well allocate a chunk of nodes in one go (and have them in contiguous memory) and then set the pointers to next to individual members of the chunk. A pointer is just a pointer and it does not determine how the memory it points to was obtained.

[napkinsterror]

can you explain why we malloc() and free() for the str field, but not for the next field? I am going to eventually put an address for this node to point to (in most cases). So I am led to believe I need to malloc() space for it. I think this might be at the root of my misunderstanding of linked lists in C. Thanks again!

[Weather Vane]

@napkinsterror initialise the next field to NULL, or the current list head (depending on your method). Otherwise you'll have an infinite task with that one's next field.

[WhozCraig]

"Where does the memory for y come from now" - the same place the memory for x came from. They're both automatic variables. The difference is what each is intended to hold. x holds an int value, y holds an address that, properly determined, refers to memory that holds an int value. Nor does the latter have to be dynamic. One could just as easily int x = 5; int *y = &x;. Ultimately a pointer variable holds an address. The source of that address, be it dynamic or not, determines how it should eventually be managed.

[BLUEPIXY]

@napkinsterror but not for the next field? next delegate to List_destroy(list->next);.