A dynamic array

Why this matters

C arrays have a size fixed when they are created. Real programs rarely know in advance how many lines a file has, how many users are connected, or how many words a document contains. Every higher-level language has a growable list built in: Python's list, C++'s std::vector, Rust's Vec, Java's ArrayList. All of them are the structure in this lesson, a dynamic array. In C you build it yourself from malloc, realloc and a struct, and doing so teaches the pattern that every data structure in this module follows: a struct that owns heap memory, a small set of functions that keep it consistent, and one function that frees it.

The idea: length and capacity

You met growing buffers in the dynamic memory module. A dynamic array packages that technique behind an interface. It keeps three pieces of information together:

typedef struct {
    int *data;      /* heap block of cap ints, or NULL */
    size_t len;     /* elements in use: data[0] .. data[len-1] */
    size_t cap;     /* elements allocated */
} IntVec;

  IntVec v (on the stack)            heap block (cap = 8)
  +------------------+              +----+----+----+----+----+----+----+----+
  | data  o----------+------------> | 1  | 4  | 9  | 16 | 25 | ?  | ?  | ?  |
  | len   5          |              +----+----+----+----+----+----+----+----+
  | cap   8          |                 in use (len = 5)      | spare capacity
  +------------------+

The invariant, the rule that is always true between calls, is len <= cap, and data points to a block big enough for cap elements (or is NULL when cap is 0). Elements 0 to len - 1 hold meaningful values; the rest is spare room that lets the next few pushes happen without allocating.

Growing geometrically

When len == cap and another element arrives, the array must grow. The crucial decision is by how much:

• Grow by one (or any fixed amount): every few pushes copy the entire array. Pushing n elements costs on the order of n * n / 2 copies, which for a million elements is hundreds of billions.
• Grow by a factor (double, or 1.5x): copies happen only at sizes 4, 8, 16, 32, ... and the total number of copies is less than 2n. On average each push costs a constant amount of work, even though an occasional push is expensive. This is called amortized O(1).

Here is the complete type with initialization, push, a checked accessor and cleanup:

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

typedef struct {
    int *data;
    size_t len;
    size_t cap;
} IntVec;

void vec_init(IntVec *v)
{
    v->data = NULL;
    v->len = 0;
    v->cap = 0;
}

int vec_push(IntVec *v, int value)
{
    if (v->len == v->cap) {
        size_t new_cap = v->cap ? v->cap * 2 : 4;
        int *tmp = realloc(v->data, new_cap * sizeof *tmp);
        if (tmp == NULL)
            return -1;          /* v is unchanged and still valid */
        v->data = tmp;
        v->cap = new_cap;
    }
    v->data[v->len++] = value;
    return 0;
}

int vec_get(const IntVec *v, size_t i, int *out)
{
    if (i >= v->len)
        return -1;
    *out = v->data[i];
    return 0;
}

void vec_free(IntVec *v)
{
    free(v->data);
    vec_init(v);                /* back to a valid empty state */
}

int main(void)
{
    IntVec v;
    vec_init(&v);
    for (int i = 1; i <= 10; i++) {
        if (vec_push(&v, i * i) != 0) {
            fprintf(stderr, "out of memory\n");
            vec_free(&v);
            return 1;
        }
        printf("push %3d  len=%2zu cap=%2zu\n", i * i, v.len, v.cap);
    }
    int x;
    if (vec_get(&v, 9, &x) == 0)
        printf("v[9] = %d\n", x);
    if (vec_get(&v, 10, &x) != 0)
        printf("v[10] is out of range\n");
    vec_free(&v);
    return 0;
}

push   1  len= 1 cap= 4
push   4  len= 2 cap= 4
push   9  len= 3 cap= 4
push  16  len= 4 cap= 4
push  25  len= 5 cap= 8
push  36  len= 6 cap= 8
push  49  len= 7 cap= 8
push  64  len= 8 cap= 8
push  81  len= 9 cap=16
push 100  len=10 cap=16
v[9] = 100
v[10] is out of range

Under valgrind it reports no errors and no leaks. Points worth noticing:

• The struct lives wherever you like (here on the stack); only the elements are on the heap. Functions take an IntVec * so they can update len, cap and data in the caller's struct.
• realloc(NULL, n) acts like malloc(n), so the very first push needs no special case.
• realloc goes into a temporary. If it fails, the old block is still valid and still owned by v; the function reports failure and the caller decides what to do.
• vec_get checks the index and reports through a return code, because C has no exceptions. Many real implementations skip the check for speed and document "index must be valid" instead; either way the rule must be written down.
• vec_free leaves the struct usable, as an empty array, so a second vec_free is harmless.

Inserting and removing in the middle

Appending is cheap. Inserting at index i means every element from i onwards must move one place to the right, which costs O(n):

  insert 7 at index 1:

  before   [ 3 | 5 | 9 | . ]       len 3
  shift    [ 3 | 5 | 5 | 9 ]       memmove data[1..2] to data[2..3]
  store    [ 3 | 7 | 5 | 9 ]       len 4

The source and destination ranges overlap, so use memmove, which is defined to handle overlap correctly. memcpy with overlapping ranges is undefined behavior; with some sizes it really does corrupt data. Removing is the mirror image: shift the later elements left over the removed one.

If order does not matter, there is an O(1) removal trick: copy the last element into the hole and decrease len. Many game engines and schedulers use this "swap remove".

Pointer invalidation

Because vec_push may move the whole block, any pointer into the array becomes dangling after a push:

int *first = &v.data[0];
vec_push(&v, 42);       /* may realloc and move the block */
printf("%d\n", *first); /* possibly reading freed memory */

This is the same rule as with realloc (and as std::vector iterator invalidation in C++). Hold on to indexes into a dynamic array, not pointers.

Making it generic

IntVec only stores int. C has no templates, so generic containers usually store an element size and use void * with memcpy, the same way qsort works:

typedef struct {
    void *data;
    size_t len, cap, elem_size;
} Vec;
/* push copies elem_size bytes from a pointer:  vec_push(&v, &value) */

The price is lost type checking and a memcpy per access. Another common approach is a macro that generates a typed version for each element type. For learning, a typed IntVec is clearest.

Common mistakes

• Growing by a constant. Correct but quadratic; it becomes visibly slow at tens of thousands of elements.
• v->data = realloc(v->data, ...): on failure the only pointer to the block is lost (a leak), and v->data is NULL while len still says there are elements.
• Forgetting to update cap after growing, so the next push grows again or, worse, the code thinks there is more room than there is.
• Using memcpy for overlapping shifts. Use memmove.
• Off-by-one in the shift length. The number of elements to move when inserting at i is old_len - i. Sanitizers or valgrind catch the overrun if you get it wrong.
• Keeping pointers into the array across pushes.

Recap

• A dynamic array is a struct with data, len and cap, and the invariant len <= cap.
• Grow geometrically (doubling) for amortized O(1) appends; a fixed step is quadratic.
• Call realloc through a temporary; on failure the old block is untouched.
• Insert and remove in the middle are O(n) and need memmove.
• Pushing can move the block: keep indexes, not pointers.

Going further: measure it. Time pushing 10 million ints with doubling versus growing by 16 (time ./prog in the sandbox terminal). Then read how CPython grows lists: list_resize in Objects/listobject.c uses a factor of about 1.125 plus a constant, trading memory for copies.