C: amortized cost of a growing array

A fixed-size C array cannot grow, so programs that do not know their size in advance keep a pointer to heap memory, a size, and a capacity. When size reaches capacity, the program allocates a larger block, copies the elements across, and frees the old block.

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

typedef struct {
  int *data;
  size_t size;
  size_t capacity;
  long copies;
} IntList;

static void add(IntList *list, int value) {
  if (list->size == list->capacity) {
    size_t bigger = list->capacity == 0 ? 1 : list->capacity * 2;
    int *grown = malloc(bigger * sizeof *grown);
    if (grown == NULL) {
      exit(1);
    }
    for (size_t i = 0; i < list->size; i++) {
      grown[i] = list->data[i];
      list->copies++;
    }
    free(list->data);
    list->data = grown;
    list->capacity = bigger;
  }
  list->data[list->size++] = value;
}

int main(void) {
  IntList list = {NULL, 0, 0, 0};
  for (int i = 1; i <= 16; i++) {
    add(&list, i);
  }
  printf("appends=16 copies=%ld\n", list.copies);
  printf("copies per append=%.4f\n", (double)list.copies / 16);
  free(list.data);
  return 0;
}

Read the full lesson