Implementing Dynamic Arrays in C: From Compile-Time Determination to Runtime Allocation

Basic Mechanisms of Array Size Determination

In C, arrays are fundamental data structures whose sizes must be determined at creation time. According to the C standard, array sizes can be determined in two ways: at compile time via constant expressions, or at runtime via variables (supported in C99 and later). Once an array is created, its size is fixed and cannot be dynamically increased or decreased.

Array Definitions Without Explicit Size Specifiers

In certain cases, the size specifier for the leftmost dimension can be omitted in array definitions if an initializer is provided. The compiler infers the size from the initializer. For example:

int a[] = { 1, 2, 3 };              // Equivalent to int a[3] = { 1, 2, 3 };
int m[][2] = {{ 1, 2 }, { 3, 4 }};  // Equivalent to int m[2][2] = {{ 1, 2 }, { 3, 4 }};
char s[] = "Hello world\n";         // Equivalent to char s[13] = "Hello world\n";

In string initialization, the compiler automatically adds an implicit null terminator, so the array size is one element larger than the string literal length.

Array Declarations Without Size Specifiers

Omitting the size specifier for the leftmost dimension in array declarations is allowed in several contexts, but the compiler lacks information about the actual size; programmers must determine the length through other means:

• As a global variable with extern storage class (the array is defined elsewhere).
• As a function parameter: e.g., int main(int argc, char *argv[]). In this case, any specified size for the leftmost dimension is ignored because the array is passed as a pointer.
• As the last member of a struct with more than one named member (a C99 extension known as a flexible array member).

For function parameters, even if the number of elements is specified, sizeof(argv) evaluates to the size of a pointer, not the array.

Dynamic Memory Allocation for Variable-Size Arrays

When the array size is only known at runtime, pointers and dynamic memory allocation functions can simulate dynamic array behavior. The basic approach is to declare a pointer and allocate memory at runtime using malloc or calloc:

int* bills;
bills = (int*)malloc(sizeof(int) * items);

This method allows memory to be allocated and freed as needed during program execution but requires manual memory management to avoid leaks and illegal access.

Dynamic Array Resizing

To dynamically increase array capacity during program execution, combine malloc, realloc, and free. A common strategy is to allocate memory in fixed-size blocks and use realloc to expand memory when the current allocation is insufficient:

#define BLOCK_SIZE 10
int *ptr = malloc(sizeof(int) * BLOCK_SIZE);
if (ptr == NULL) {
    perror("Memory allocation failed");
    return 1;
}
int max_index = BLOCK_SIZE - 1;

for (int i = 0; ; ++i) {
    if (i > max_index) {
        ptr = realloc(ptr, (max_index + 1 + BLOCK_SIZE) * sizeof(int));
        if (ptr == NULL) {
            perror("Insufficient memory");
            break;
        }
        max_index += BLOCK_SIZE;
    }
    // Process array elements
}
free(ptr);

This approach minimizes performance overhead from frequent reallocations by allocating memory in blocks as needed, maintaining array dynamism.

Summary and Best Practices

C does not natively support dynamically sized arrays, but similar functionality can be achieved using pointers and dynamic memory management functions. The choice of method depends on specific needs: use static arrays if the size is known at compile time or creation; use malloc for runtime-determined fixed sizes; and use realloc for dynamic resizing. Regardless of the method, careful memory management is essential to ensure allocated memory is properly freed, avoiding leaks and illegal access.