We have learned the basics of using malloc and free to dynamically allocate and deallocate blocks of memory. In this video we will demonstrate using malloc and free on a nested data structure.

Let's imagine that we need a nested array: an array of pointers, where each element may itself point to an array.

In this case, the first pointer refers to a single integer, and the second points to an array of 3 integers. While this example is small, this is a fairly common structure. We often need an array where we don't know the length -- or the size of the elements -- before runtime. Since we don't know the sizes at compile time, we have to use dynamic memory, rather than statically-defined arrays.


First, we'll create the top-level array. We need to do this first so that we have a place to store the pointers for our sub-arrays.

We want to create this data-structure dynamically, so we use malloc to allocate the appropriate space.

In our top-level array, we need enough space for two pointers and each one is sizeof(int *).

Since we are creating an array where each element is int *, and we access arrays by using a pointer to the first element, we need a pointer to an int * which is type int **.

Now, we need to allocate the subarrays. We'll allocate each one individually.

To allocate space for the single integer, we need to malloc a single integer. We assign the pointer that is returned to pointers[0].

We still haven't allocated any space for this array of 3 integers.

To do that we call malloc again asking for enough space for 3 integers and assigning the returned address to pointers[1].

Now we have the space fully allocated, so let's set the values of some of the integers.

This statement says to take the 0th element of the array of pointers

-- that's the first int * pointer in our array,

dereference it, and set it's value to 55;

We could have used this array syntax to accomplish the same thing. Array syntax often feels more natural than dereferencing.

Now, let's modify the next element.

Here we look at the 2nd element of the pointer array.

In particular, the 3rd element of the sub-array.

We set it to 300.

At some point, we'll finish using the data structure and will need to free the memory.

You can probably see right away that we need to call free(pointers) but that's not enough.

Each call to malloc needs to be freed separately. When we free pointers, we're freeing the top-level array, but we have two other malloc'd objects that need to be freed.

What's worse, if we free the top-level array first, then we can't access the sub-arrays without using a dangling pointer.

So we have to free the sub-arrays first.

Our little data structure of one integer and one array of 3 integers wasn't terribly complicated, but it still demonstrated the need to free memory carefully.

Each time you put a malloc statement into your code you need to carefuly consider when and where it is safe to deallocate the memory. If the memory is going to be used throughout the program, you may be ok without explicitly freeing the memory -- it will be freed when the program terminates. However, in general, each malloc statement should have a corresponding free statement somewhere in your program. Good practice is to write the free statement at the same time as you write the malloc, so that you don't forget. In addition, as we saw in this example, you'll typically need to create data structures from the top down and to free them in the opposite order.