C: amortized cost of a growing array

Double the capacity of a malloc'd array when it fills, and count the copies made.

#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;
}

Output

appends=16 copies=15
copies per append=0.9375

Explanation

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.

If the new capacity is a constant amount larger, n appends cost O(n²) in total. If it doubles, the copies are 1 + 2 + 4 + ... which is less than 2n, so each append is amortized O(1). This is the strategy behind C++ std::vector and Java ArrayList. The program counts element copies for 16 appends.

Explore the dry run

Guided walkthroughReady

1#include <stdio.h>

2#include <stdlib.h>

4typedef struct {

5 int *data;

6 size_t size;

7 size_t capacity;

8 long copies;

9} IntList;

11static void add(IntList *list, int value) {

12 if (list->size == list->capacity) {

13 size_t bigger = list->capacity == 0 ? 1 : list->capacity * 2;

14 int *grown = malloc(bigger * sizeof *grown);

15 if (grown == NULL) {

16 exit(1);

17 }

18 for (size_t i = 0; i < list->size; i++) {

19 grown[i] = list->data[i];

20 list->copies++;

21 }

22 free(list->data);

23 list->data = grown;

24 list->capacity = bigger;

25 }

26 list->data[list->size++] = value;

27}

29int main(void) {

30 IntList list = {NULL, 0, 0, 0};

31 for (int i = 1; i <= 16; i++) {

32 add(&list, i);

33 }

34 printf("appends=16 copies=%ld\n", list.copies);

35 printf("copies per append=%.4f\n", (double)list.copies / 16);

36 free(list.data);

37 return 0;

38}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
The capacity doubles: 1, 2, 4, 8, 16.	`capacity doubles when full`	—
Every existing element is copied once per growth step.	`copies = 1 + 2 + 4 + 8 = 15`	—
The old block is released. Forgetting this would leak memory.	`copies = 1 + 2 + 4 + 8 = 15`	—
Fifteen copies over sixteen appends is under one copy per append.	`copies = 1 + 2 + 4 + 8 = 15`	appends=16 copies=15 copies per append=0.9375

Cost and common mistakes

Each add is amortized O(1); n adds take O(n) time and O(n) space.

malloc can return NULL. A real program checks for it and does not write through a null pointer.
realloc can grow a block in place and is usually better than malloc, copy, and free. It may move the block, so always assign its result to a temporary pointer first.
Pointers into the old block become invalid after growth, so do not keep them.

Try it yourself

How many copies are needed for 8 appends?

Reveal answer and reasoning

7 copies (1 + 2 + 4), which is again fewer than the number of appends.

C: amortized cost of a growing array

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading