C in 100 Seconds: Dynamic Arrays

Dynamic Arrays — Grow on Demand

C arrays have a fixed size. A dynamic array starts small and grows when it runs out of room. Double the capacity each time for amortized O(1) appends.

The Struct

typedef struct {
  int *data;
  int size;
  int capacity;
} DynArray;

Three fields — a pointer to the heap buffer, how many elements are stored, and the total allocated capacity.

Push with Auto-Grow

void push(DynArray *a, int val) {
  if (a->size == a->capacity) {
    a->capacity *= 2;
    a->data = realloc(a->data, a->capacity * sizeof(int));
  }
  a->data[a->size++] = val;
}

When size equals capacity, double the capacity and realloc. Then store the value and bump size. realloc either extends the existing block or moves it to a bigger one.

Output

capacity: 2
  (grew to 4)
  (grew to 8)
size: 5, capacity: 8
10 20 30 40 50

Started at two, grew to four at the third push, grew to eight at the fifth. Always free the data pointer when done.

Student code: GitHub