How do I declare an array of undefined or no initial size?

The way it's often done is as follows:

  • allocate an array of some initial (fairly small) size;
  • read into this array, keeping track of how many elements you've read;
  • once the array is full, reallocate it, doubling the size and preserving (i.e. copying) the contents;
  • repeat until done.

I find that this pattern comes up pretty frequently.

What's interesting about this method is that it allows one to insert N elements into an empty array one-by-one in amortized O(N) time without knowing N in advance.


Modern C, aka C99, has variable length arrays, VLA. Unfortunately, not all compilers support this but if yours does this would be an alternative.


Try to implement dynamic data structure such as a linked list


This can be done by using a pointer, and allocating memory on the heap using malloc. Note that there is no way to later ask how big that memory block is. You have to keep track of the array size yourself.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char** argv)
{
  /* declare a pointer do an integer */
  int *data; 
  /* we also have to keep track of how big our array is - I use 50 as an example*/
  const int datacount = 50;
  data = malloc(sizeof(int) * datacount); /* allocate memory for 50 int's */
  if (!data) { /* If data == 0 after the call to malloc, allocation failed for some reason */
    perror("Error allocating memory");
    abort();
  }
  /* at this point, we know that data points to a valid block of memory.
     Remember, however, that this memory is not initialized in any way -- it contains garbage.
     Let's start by clearing it. */
  memset(data, 0, sizeof(int)*datacount);
  /* now our array contains all zeroes. */
  data[0] = 1;
  data[2] = 15;
  data[49] = 66; /* the last element in our array, since we start counting from 0 */
  /* Loop through the array, printing out the values (mostly zeroes, but even so) */
  for(int i = 0; i < datacount; ++i) {
    printf("Element %d: %d\n", i, data[i]);
  }
}

That's it. What follows is a more involved explanation of why this works :)

I don't know how well you know C pointers, but array access in C (like array[2]) is actually a shorthand for accessing memory via a pointer. To access the memory pointed to by data, you write *data. This is known as dereferencing the pointer. Since data is of type int *, then *data is of type int. Now to an important piece of information: (data + 2) means "add the byte size of 2 ints to the adress pointed to by data".

An array in C is just a sequence of values in adjacent memory. array[1] is just next to array[0]. So when we allocate a big block of memory and want to use it as an array, we need an easy way of getting the direct adress to every element inside. Luckily, C lets us use the array notation on pointers as well. data[0] means the same thing as *(data+0), namely "access the memory pointed to by data". data[2] means *(data+2), and accesses the third int in the memory block.

Tags:

C

Recent Posts