UPDATE: Thanks for all the great comments! Apparently I’m the #1 result for “C dynamic array” on Google. Pretty cool. :) It’s certainly taken me a while to get around to it, but I’ve updated this tutorial and sample code to incorporate some of your suggestions and comments. Thanks a bunch, especially to bbulkow and tinkertim!

For the purposes of education and the prospect of writing a new game, I’ve been doing some poking around in C. I’ve certainly learned a few things (and expect to learn more in the future) Prior to this, I’ve only had experience with C++, which some would argue is a completely different beast altogether. However, this post is not intended to discuss the differences between C and C++.

Anyways, I figured I might share a few snippets and wisdom that I’ve picked up along the way, so here’s a quick (?) rundown of how to use structs and pointers to create “dynamic” arrays that will resize as you need them.

Right, so let’s suppose you’ve got a struct built that you’ll use to hold some data…

typedef struct {
    char *name;
    int number;
} DATA;

And we’ll also need to set up an array, along with some variables to track how many items are in the array and how large the array is…

DATA    *the_array = NULL;
int     num_elements = 0; // Keeps track of the number of elements used
int     num_allocated = 0; // This is essentially how large the array is

What’s this? I’m not using []‘s to define the size of the array? That’s right; At this point, the array is just a pointer. We’ll need to allocate memory for each entry into the array.

So next, we need a way to add items to our array that will be mindful of the fact that it is dynamic. What is needed is a function that will do three things:

  • Initialize the array if it is not already initialized.
  • Resize the array if more space is needed.
  • Add new items to the array.

Keeping that in mind, let’s take a look at the realloc function‘s prototype:

void * realloc ( void * ptr, size_t size );

The purpose of this function is to re-allocate memory to a pointer that already has memory allocated to it. Of course, you’ll only want to use it to make memory allocations larger, otherwise you’ll risk losing data. The size parameter is the amount of memory that you want to allocate. And the other parameter, ptr, is where you’d like to allocate it to. In this case, it’ll be the TheArray pointer that we’ve defined above. What is great about realloc is that if the ptr is NULL, the function will act just like malloc. This will allow us to use this one call for both initializing and resizing the array. Check this realloc reference page for more information.

Here is my AddToArray function …

int AddToArray (DATA item)
{
        if(num_elements == num_allocated) // Are more refs required?
        { 
                // Feel free to change the initial number of refs
                // and the rate at which refs are allocated.
                if (num_allocated == 0)
                        num_allocated = 3; // Start off with 3 refs
                else
                        num_allocated *= 2; // Double the number 
                                                    // of refs allocated

                // Make the reallocation transactional 
                // by using a temporary variable first
                void *_tmp = realloc(the_array, (num_allocated * sizeof(DATA)));

                // If the reallocation didn't go so well,
                // inform the user and bail out
                if (!_tmp)
                {
                        fprintf(stderr, "ERROR: Couldn't realloc memory!\n");
                        return(-1);
                }

                // Things are looking good so far
                the_array = (DATA*)_tmp;
        }

        the_array[num_elements] = item;
        num_elements++;

        return num_elements;
}

You can see that it performs all three requirements listed above.
You may ask, ‘why is the allocation size doubling each time a resize is needed?’. This is done mainly because realloc() can be an expensive call, and if you spend a lot of time resizing your array, it could slow down the execution of your application. This way, it’s only done once in a while. Of course, feel free to fiddle with the initial allocation as well.

Also, be careful when using realloc(), as you’ll need to remember to use the free() function later on to free the memory that you’ve allocated to your program. You’ll want to run this code when you’re done using the array …

// Deallocate!
free(TheArray);

I’ve got a little example available right here:

Download Example – (arrays.c – 2kb)

It compiles and runs just fine using GCC, but I haven’t tried it with anything else, so your mileage may vary. Also, a huge special thanks to DrPetter and X-0ut for their help on this subject!

As always, comments are welcome! :)

34 Responses to “a tutorial on ‘dynamic’ arrays in C”

  1. Anthony says:

    Sorry if this is a dumb question but why would “TheArray” ever be NULL?

    if (TheArray == NULL)
    {
    fprintf(stdout, “ERROR: Couldn’t realloc memory!”);
    exit(2);
    }

  2. Anthony says:

    Sorry for not adding this into my first reply, but how do you deallocate each item in the array if you do not know the size of the array?

  3. fydo says:

    Hi Anthony! Thanks for the comments.

    I probably should have elaborated a little more in the article, but if there is insufficient memory available, the realloc() call will return NULL. Since you don’t have any control over how much free memory the user will have available, it’s a good idea to check to ensure the allocation succeeded.

    As for your second question, in my example I’ve created two variables that will track the number of elements in the array, as well as the number of elements allocated in the array. You actually don’t even need those variables for deallocation, as just passing the array to the free() function will automatically deallocate the entire array.

    Hope that helps! :)

  4. 7 says:

    thx for the tutorial it helped alot.

  5. Dennis says:

    amazing!

    I’ve learned about realloc.

  6. bbulkow says:

    @7
    Your code has two flaws, and since you’re the number one Google entry under ‘C dynamic array’, I feel moved to comment.

    First,
    When ‘realloc’ returns NULL, the input data is not freed. Thus, you’ve written a memory leak (at least, you would if the error case wasn’t ‘exit()’). It’s more common to use a metaphor like this:
    void *_tmp = realloc(TheArray, newsize);
    if (!_tmp) { fprintf(stderr,”whoa, dude, no memory\n”); return(-1); }
    TheArray = _tmp;
    thus your structure contains the data before the failed add, thus can be used if the addition isn’t fatal, and a ‘free’ of the object is uncomplicated.

    Second, TheArray is uninitialized. If you’re programming in Linux, ‘valgrind’ is a huge tool here, other analysis tools like Purify are available for other platforms.

  7. nj says:

    Hi this tutorial is highly helpful and very lucid

  8. tinkertim says:

    I would have made AddToArray() a signed int type that returned:

    – The number of elements currently in the array on success
    – 0 on a non-fatal error (i.e., DATA is in tact)
    – -1 on a fatal error (i.e. , don’t use DATA anymore and don’t try to free it)

    I also suggest the comment made by bbulkow which in essence makes realloc() (and by extension AddToArray() ) transactional.

    Beyond that … ThisIsNotJava(Its_C);

    I know .. I know .. everyone’s a ^@*&^ critic :)

  9. Gregory Kramida says:

    This kind of dynamic array only stores elements of type “DATA”, which are structs with two fields – a string and an integer. What if you want to make a dynamic array structure that supports any type of element?

    I’ve been trying to do it and ran into some weird trouble… I have another kind of field in my dynamic array for this purpose, element size, which is assigned to the array with a special initialization function. It is then used in all subsequent reallocations.

    For some reason, at some point realloc messes up my data and then outputs some memory access error (realloc?? how is that possible?)… Anyone have some sugguestions?

  10. Gregory Kramida says:

    Actually, never mind that, I got the dynamic array of variable element type to work. Anyone interested in the source can post a request here.

  11. mctayong says:

    great tutorial! this really helped me a lot! wow!

  12. thommy says:

    Shouldn’t you do num_allocated -= 3 or num_allocated /= 2 if reallocation failed? Otherwise, num_allocated is also increased if reallocation failed.
    And if you do num_allocated *= 2; each time, then you get 3, 6, 12, 24, … which will give a huge number after a few times. Or did i get something wrong?

    I modified your code as follows:
    int addToArray(DATA item) {
    //Number of refs to allocate each time
    int num_to_allocate = 100;

    // Are more refs required?
    if(num_elements == num_allocated) {
    num_allocated += num_to_allocate;

    // Make the reallocation transactional
    // by using a temporary variable first
    void *_tmp = realloc(dataArray, (num_allocated * sizeof(DATA)));

    // If the reallocation didn’t go so well,
    // inform the user and bail out
    if (!_tmp) {
    fprintf(stderr, “ERROR: Couldn’t realloc memory!\n”);
    num_allocated -= num_to_allocate;
    return(-1);
    }

    // Things are looking good so far
    dataArray = (DATA*)_tmp;
    }

    dataArray[num_elements] = item;
    num_elements++;

    return num_elements;
    }

  13. vincent says:

    i used a dynamic array in my program, here’s the fragment.

    char *data_type, *identifier;

    then after i allocated a memory for data_type[] and stored a value, and right after which i again allocated a memory for identifier[], when i checked the value of data_type[] it actually changed….appending a garbage value at the last….

    here’s the algo:

    -allocate memory for data_type
    -initialize data_type
    -store the string “void” to data_type (using puts(); i checked the value and it was exactly “void”)
    -allocate memory for identifier[] (then i again checked the value for data_type[] and it was now “voidñ”)

    …i really had a hard time looking why the value of a dynamic array changed…..and i deduced that it changed due to another allocation of a dynamic array…..so why is that so? pls….anyone…help…..

  14. Abhijeet says:

    Hi,

    this is really a great post, and solved a part of my project.. I have very
    little knowledge of C, and this was useful. Sometimes I love C++ more
    over C. :P
    @Gregory: Hey mate, can ya help me with your generic version. your help
    is much appreciated.

    Regards,

  15. Chanaka says:

    This is an excellent implementation of vector like structure in c. It really works for me.

  16. Deepanjan says:

    Hi,
    If i want to deallocate only a part of TheArray each time i do some operation.
    Is there any way to free only the last n elements of an array allocated
    using malloc/realloc?

    thanks

  17. Jason Sullivan says:

    @Gregory,
    I’m working on something quite similar and would love to see the source code.

  18. moath says:

    hi all…..
    i need help in my homework…….i’m new user of c and can’t find the solution for this question

    write aprogram that reads information about 20 employees and store it in adynamic array of structuer.the structer of each employee should contain:name(dose not exceed19 characteres)
    id(int),salary(double) between 200&4000 ,and address.the program should then output the following:
    1 the average of employee salaries
    2the mames of employees tax amount ,given that tax amount is 10%of the salary for salaries above 1000 and 5% for salaries below or equal to 1000
    the number of embloyees whose names starts with’a’

  19. Rey says:

    i have a question about bbulkow… sorry, i’m a noob coder… any way..
    the code he suggested is similar to what fydo has written…. right?
    and what does he mean by “When ‘realloc’ returns NULL, the input data is not freed. Thus, you’ve written a memory leak (at least, you would if the error case wasn’t ‘exit()’).”

    thanks… great tutorial!! ^_^

  20. ulrich says:

    I believe there is a major flaw in this code: realloc() does NOT guarantee that the
    newly allocated memory starts at the same address as the “old” allocation. How could
    it? If you do more than one malloc(), there will only be limited unused space (if
    any) after the memory block allocated by the first call to malloc().

    Thus, you need to check for this and if the addresses differ, you need to copy the
    old elements to the new location. Note that any pointers into the array i.e. to
    elements of the array then become invalid.

    This comment will also answer the question raised by Kramida: “For some reason, at some point realloc messes up my data and then outputs some memory access error (realloc?? how is that possible?)… Anyone have some sugguestions?”

    Best,

    ulrich

  21. Simon says:

    Do you think there is any way to resize (downsize) the array?

    I would like to create an array where data is added dynamically and when the element has been treated by the program the memory is freed.

    I am programming in C# and I cannot use any of the C++ STD lib.

  22. Sandeep says:

    thanks for posting this. saved me some time.

  23. Nilesh says:

    Man thanks a million!
    I was struggling with dynamic structure array since last three days!
    This tutorial has helped me like anything.
    Thanks Thanks Thanks Thanks.

  24. glicholas says:

    By using this example I was able to implement an array made of doubles to represent x and y coordinates. I was able to read in an unknown amount and take all data. It worked for thousands and thousands of members. This is the most clear and precise example I was able to find anywhere on the net. Thanks a bunch!

  25. Good work!
    If you want to be able to use more than one dynamic array in a program, it’s a good idea to turn the array into a struct type.
    You can store elements of any type if you make the array an array of void pointers.
    I’ve written an implementation which you can find here:
    http://www.martinbroadhurst.com/articles/dynamic-array.html

  26. I should add that the main disadvantage of dynamic arrays is that each time you reallocate, the contents of the buffer need to be copied. If your array starts off small and gets very large, this copying can really impact on performace.
    One solution is to have a dynamic array of arrays, and store the elements in the arrays. When you run out of space, you just add another array. You can have the size of each array larger than the previous one, so that you still double the capacity at each allocation, but no copying is involved.
    I have written an implementation of this strucure here:
    http://www.martinbroadhurst.com/articles/list-as-a-dynamic-array-of-increasing-sized-arrays.html

  27. Frank says:

    This code is giving a bunch of warnings and errors when trying to compile it:

    test.c:4: warning: parameter names (without types) in function declaration
    test.c: In function ‘addToArray’:
    test.c:40: error: ‘num_elements’ undeclared (first use in this function)
    test.c:40: error: (Each undeclared identifier is reported only once
    test.c:40: error: for each function it appears in.)
    test.c:40: error: ‘num_allocated’ undeclared (first use in this function)
    test.c:48: error: ‘the_array’ undeclared (first use in this function)

    The errors seem obvious, but I’m wondering how you’re using the function to avoid them? Seriously, when you make a tutorial like this, it would be a good idea to include an actual working example of implementing it.

  28. fydo says:

    Frank,

    I’m not getting any of those errors when compiling the code example using GCC 4.4.3. What compiler are you using?

  29. Erik says:

    @ulrich: While you’re right in that the pointer address might change as a new region in memory is allocated, realloc guarantees that the data is moved properly and the old memory freed. Thus, you don’t need to copy the data yourself (it is an error to do this: you’re accessing memory that has been free’d by realloc()).

  30. tavaris says:

    Lets say you have to dynamically allocate an array of structs and you have to read a number in from an input file that tells you how big the array is going to be. How would you do that?

  31. [...] get rid of this advertisement]'); I'm writing an addToArray function in C like the one described here. However, instead of passing struct of type DATA to this function, I want to pass a pointer to a [...]

  32. [...] }); I'm writing an addToArray function in C like the one described here. However, instead of passing struct of type DATA to this function, I want to pass a pointer to a [...]

  33. Ahmed Fayed says:

    Thanks!! this is really helpful :)

  34. Anthony Perks says:

    y’know, for a cat, you’re really clever.

Leave a Reply