Skip to content

Intermediate · Dynamic memory · topic 28 of 60 · 30 min

realloc and growing arrays

Explanation

realloc(p, new_size) resizes a heap block, possibly moving it to a new address and copying the contents. If it fails it returns NULL and leaves the old block alive, so always assign the result to a temporary first. A dynamic array keeps a size and a capacity and doubles the capacity when full, which makes adding n items cost O(n) in total (amortised O(1) each).

Why grow?

When reading data of unknown length (lines from a file, items from a network), you cannot know the size in advance. Allocating a huge fixed array wastes memory or still might not be enough. Instead, start small and grow the block when it fills up.

realloc

c
int *a = malloc(4 * sizeof *a);
/* … a is full … */
int *tmp = realloc(a, 8 * sizeof *a);     /* try to grow to 8 ints */
if (tmp == NULL) {
    /* a is STILL valid here; handle the error and eventually free(a) */
    free(a);
    return 1;
}
a = tmp;                                  /* may be a different address now */
Careful: Writing a = realloc(a, new_size); leaks the original block when realloc fails, because the only pointer to it is overwritten with NULL. Always use a temporary. Also, after a successful realloc, any OTHER pointers into the old block are dangling, because the data may have moved.

A dynamic array (like a vector)

c
typedef struct {
    int *data;
    size_t size;       /* elements in use */
    size_t capacity;   /* elements allocated */
} IntVec;

int vec_push(IntVec *v, int value) {
    if (v->size == v->capacity) {
        size_t new_cap = v->capacity ? v->capacity * 2 : 4;   /* double (start at 4) */
        int *tmp = realloc(v->data, new_cap * sizeof *tmp);
        if (!tmp) return -1;
        v->data = tmp;
        v->capacity = new_cap;
    }
    v->data[v->size++] = value;
    return 0;
}

void vec_free(IntVec *v) { free(v->data); v->data = NULL; v->size = v->capacity = 0; }

IntVec v = {0};                              /* empty: data NULL, size 0, capacity 0 */
for (int i = 0; i < 10; i++) vec_push(&v, i * i);
printf("%zu items, capacity %zu\n", v.size, v.capacity);   /* 10 items, capacity 16 */
vec_free(&v);
realloc(NULL, n) behaves like malloc(n), so the first push works without a special case.

Why doubling?

output
capacity:  4 → 8 → 16 → 32 → …
copies when growing to hold 32 items: 4 + 8 + 16 = 28 element copies
in general: fewer than 2n copies for n pushes → O(1) per push on average ("amortised")
growing by +1 each time instead: 1 + 2 + 3 + … + (n-1) ≈ n²/2 copies → very slow

Many standard libraries (C++ std::vector, Java ArrayList, Python list) use this same idea, with growth factors between about 1.5 and 2.

Shrinking and other uses

realloc can also shrink a block (for example to trim a buffer to its final size). realloc(p, 0) has implementation-defined behaviour in older C and is undefined in C23, so do not use it to free; call free.

Think of it like this: A dynamic array is like a school that rents a hall for an event: when more students register than seats, it rents a hall twice as big and moves everyone over. Moving is tiring, but because the hall doubles each time, moves become rare as the event grows.
Tip: Keep size and capacity together with the pointer in one struct, and never let other code hold raw pointers into data across a push, because a push may move the block.

Need help?

Stuck on a word or an idea? Search this course, or every course, and jump straight to the explanation or a worked question.

Try:

Watch the lesson

realloc and growing arrays · 1/6

realloc and dynamic arrays

In this lesson you will grow heap blocks and build a dynamic array.

Prefer a video by a teacher? Find free videos on “c realloc dynamic array vector implementation amortized doubling” on YouTube ↗

In real life: Reading an unknown number of transactions

A bank statement importer does not know how many transactions a file holds. It pushes each amount into a growable array, starting with capacity 4 and doubling, so a 3-line file and a 300,000-line file both work with little wasted memory.

c
IntVec amounts = {0};
long value;
while (fscanf(fp, "%ld", &value) == 1) {
    if (vec_push(&amounts, (int) value) != 0) { perror("out of memory"); break; }
}
printf("Read %zu transactions\n", amounts.size);
vec_free(&amounts);

Practice (0/3 done)

Task 1 · Question

What is wrong with: buf = realloc(buf, bigger);

Task 2 · Code · Javascript

Simulate the doubling strategy in JavaScript, which runs here: write simulatePushes(n) that starts with capacity 0 and size 0; before each push, if size equals capacity, the new capacity is (capacity ? capacity * 2 : 4) and all current elements are copied (add size to a copies counter). Return { capacity, copies } after n pushes.

Task 3 · Practice

Implement the IntVec dynamic array in C with vec_push, vec_get (returning -1 and an error code for a bad index) and vec_free. Read numbers from standard input until end of input, push them all, print the count, the capacity and the sum, then free. Check it with valgrind or AddressSanitizer.

Quick quiz

Question 1

1.After a successful realloc, can the block have a new address?

Question 2

2.What is realloc(NULL, 100) equivalent to?

Question 3

3.Why double the capacity instead of adding 1 each time?

Question 4

4.Starting from capacity 4 and doubling, what is the capacity after 9 pushes?

Read more (free)

Before this, learn

This topic builds on these. If something here feels new, open them first.

Open a question to see the answer and why. The first ones are this topic's own quiz, so try the quiz above before you peek.

After a successful realloc, can the block have a new address?

Answer: Yes; the old contents are copied there

Use the returned pointer from then on.

What is realloc(NULL, 100) equivalent to?

Answer: malloc(100)

It allocates a new block.

Why double the capacity instead of adding 1 each time?

Answer: It keeps the total copying cost O(n), so each push is O(1) on average

Growing by 1 costs about n²/2 copies.

Starting from capacity 4 and doubling, what is the capacity after 9 pushes?

Answer: 16

4 → 8 → 16.

Why is push_back called "amortised O(1)"?Related

Answer: Occasional reallocations are spread over many cheap pushes because capacity grows geometrically

Doubling (or 1.5×) growth keeps the average cost per push constant.

From std::vector in depth

What is the main advantage of std::vector over a C-style array?Related

Answer: Its size can change at run time and it knows its size

vector grows with push_back and reports size(); it also manages its own memory.

From Arrays, std::array and a first look at std::vector

Why is list.append O(1) amortised and not O(1) every time?Related

Answer: Occasionally the list is full and must be copied to a bigger block

Most appends use spare room; a few trigger an O(n) copy. Averaged over many appends, the cost is O(1).

From Space complexity and amortised cost

How many frees does an array of 5 row pointers (each row malloc'd) need?Related

Answer: 6

5 rows + the pointer array.

From Dynamic strings and 2D arrays

Pass the quiz (60% or more) or mark this topic as done when you are ready.

Your progress is saved on this device only.

Next: Memory leaks and other heap bugs →

Next steps

  1. 2 more topics in “Dynamic memory” before its exam: Memory leaks and other heap bugs, Dynamic strings and 2D arrays.
  2. Module 6 exam: Dynamic memory · 12 questions · 25 min, without help. 5 topics of this module still to finish first.
  3. Then the next module, Structs, unions, enums and files. 60 topics left in the course before the final exam.

← Previous: malloc, calloc and free