Skip to content
Tutorials Center
My learning

Topics

Lesson 56 of 135 ยท Memory Management

Building a Dynamic Array

Build a growable array in C - a vector of ints with capacity doubling, push, insert and remove, then a generic version with void pointers and an element size.

C arrays have a fixed length. Once you write int scores[100];, you get exactly 100 slots, no more. Real programs rarely know their sizes in advance: lines in a file, results of a search, players who join a game. Languages like Python, Java and C++ solve this with a built-in growable list (list, ArrayList, std::vector). C has none, so C programmers build one. It's one of the most useful little data structures you'll ever write, and building it puts everything from the last three lessons to work: malloc and realloc, ownership, and avoiding memory errors.

In this lesson you'll build a dynamic array (also called a vector) in stages: first a vector of int with push, get and capacity doubling; then insert and remove; and finally a generic version that stores elements of any type using void * and an element size, the same technique the standard library's qsort uses.

The idea: length versus capacity

A dynamic array keeps three things together:

  • data: a pointer to a heap block holding the elements,
  • length: how many elements are in use,
  • capacity: how many elements the block can hold.

Adding an element when length < capacity is just a store and an increment. When the array is full, you realloc the block to a larger capacity first. The key decision is how much larger. Growing by one slot each time would copy the whole array on every push, which makes building an array of n elements take about nยฒ/2 copies. Growing by a constant factor (doubling is the classic choice) makes reallocations rare: the total copying work stays below 2n, so each push costs O(1) amortized time.

Since the three fields belong together, you'll keep them in a struct. Structures are the next chapter, but you need just two pieces of syntax here: struct name { ... }; declares a record type, and v->length reaches a member through a pointer v (covered fully in Structures and Pointers).

Stage 1: a vector of ints

Here's a complete, small vector type. Read the functions first, then run it.

C IntVec with push and capacity doubling

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The program finds 17 primes below 60 and grows its capacity only four times: 0 to 4, 4 to 8, 8 to 16 and 16 to 32. Some design choices worth noticing:

  • The struct starts empty. data = NULL with capacity 0 needs no allocation at all, and it works because realloc(NULL, n) behaves like malloc(n). An unused vector costs nothing.
  • Functions take IntVec *. They need to modify the caller's struct, so they receive its address (the out-parameter pattern).
  • Errors are reported, not hidden. intvec_push returns false if memory runs out, and the vector is still valid in that case because reserve only replaces data after realloc succeeds.
  • intvec_free resets the struct, so using it afterwards behaves like an empty vector rather than a dangling one.
  • reserve is public. If you know you'll add 10,000 items, one intvec_reserve(&v, 10000) call avoids all intermediate growth.

Note: the typedef struct { ... } IntVec; form lets you write IntVec instead of struct IntVec. See typedef for when that helps and when it hides too much.

Why doubling is fast

It's worth convincing yourself that doubling really keeps pushes cheap. This program counts how many elements realloc might have to copy (the old length at each growth) while pushing a million values, comparing doubling with growing by a fixed 1,000 slots:

C Counting the copying work

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Doubling copies 1,048,572 elements in total, about one copy per push. Growing by 1,000 slots copies 499,500,000, nearly 500 per push, and the gap widens as n grows: it's the difference between linear and quadratic work. (In practice realloc can sometimes grow a block in place without copying, but you can't count on it.) Some libraries use a factor of 1.5 instead of 2, trading a little more copying for less wasted capacity; any constant factor greater than 1 gives amortized O(1) pushes.

Stage 2: insert, remove and pop

Pushing at the end is the fast path. Inserting at position i means shifting every element from i onward one slot to the right, and removing means shifting them left. Because the source and destination overlap, you must use memmove, not memcpy (see String Functions).

C Insert and remove with memmove

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

IntVec v = {0}; is a shortcut for an empty vector: every member becomes zero or NULL. The run shows [10, 20, 30, 40, 50], then [5, 10, 20, 30, 40, 50], [5, 10, 20, 25, 30, 40, 50], removes 10, pops 50, and rejects the out-of-range insert. Every index from outside is validated, so a bad call returns false instead of overrunning the buffer.

Inserting or removing near the front costs O(n) because of the shifting, while working at the end is O(1). If order doesn't matter, a classic trick removes in O(1): copy the last element into the hole and shrink the length by one ("swap remove").

Stage 3: a generic vector

IntVec works only for int. You could copy it for double, then for every struct type, but C offers a more general approach: store elements as raw bytes. The vector doesn't need to know the type, only each element's size. The caller passes pointers to elements as void *, and the vector copies elem_size bytes with memcpy. This is exactly how qsort and bsearch handle any type (see void Pointers and Generic Code).

C A generic Vec for any element type

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The same Vec code stores both double values (average 20.62) and Point structs. A few details make it correct:

  • Storage is unsigned char * so that v->bytes + index * v->elem_size is plain byte arithmetic. Arithmetic on void * is a GCC extension, not standard C.
  • vec_push checks that new_capacity * elem_size can't overflow size_t before calling realloc.
  • memcpy copies exactly elem_size bytes, so any type works, including structs. The block returned by realloc is suitably aligned for every type, and every element starts at a multiple of elem_size, so the returned pointers are properly aligned too.
  • vec_at returns a void * that the caller converts to the right type. Nothing checks that the type matches, which is the price of this approach.

Warning: a pointer returned by vec_at is only valid until the next push. If the push reallocates, the data moves and the old pointer dangles. Hold on to indexes, not element pointers, across pushes.

Trade-offs of the generic approach

The void * vector is flexible but gives up type safety: pushing an int into a vector of double compiles without complaint and silently stores the wrong bytes. Calls also go through memcpy with a run-time size, which is slightly slower than a typed store (optimizers often recover most of the gap).

Large C projects use a few alternatives:

Approach Type safety Speed Downside
One typed vector per element type (IntVec) Full Best Duplicated code
void * + element size (Vec) None Good Casts and no type checking
Macros that generate a typed vector per type Full Best Harder to read and debug

The macro technique writes a #define that expands into a whole typed struct and its functions for any type you name; you'll have the tools to build it after Macros. C23's typeof also helps write type-checked helper macros on top of a generic core.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A dynamic array has length 8 and capacity 8, and grows by doubling. What are length and capacity after one more push?

    The array is full, so it grows to 16 slots first, then the new element makes the length 9.
  2. 2. Why does growing by a constant factor (like doubling) give O(1) amortized pushes, while growing by a fixed number of slots does not?

    Copy sizes form a geometric series (4 + 8 + 16 + ... < 2n) with doubling, but an arithmetic series (about nยฒ / (2 ร— step) copies) with fixed steps.
  3. 3. Why does intvec_insert use memmove instead of memcpy to shift elements?

    memcpy with overlapping ranges is undefined behavior. memmove behaves as if it copied through a temporary buffer.
  4. 4. Point *p = vec_at(&path, 0); then several vec_push(&path, ...) calls, then p->x = 1;. What is the problem?

    realloc can move the block. Re-fetch the pointer with vec_at after pushing, or keep the index.
  5. 5. Why does the generic Vec store its data as unsigned char * instead of void *?

    The standard doesn't define arithmetic on void *. With unsigned char *, adding index * elem_size moves exactly that many bytes.

Summary

  • A dynamic array keeps data, length and capacity together and reallocates only when length reaches capacity.
  • Grow by a constant factor (usually 2): total copying stays linear, so pushes are O(1) amortized. Fixed-size growth is quadratic.
  • Start empty (NULL, capacity 0) and rely on realloc(NULL, n); replace data only after realloc succeeds, so a failure leaves the vector valid.
  • Insert and remove shift elements with memmove and cost O(n); validate every index.
  • A generic vector stores raw bytes plus an element size, copies with memcpy, and checks the size multiplication for overflow. It trades type safety for flexibility.
  • Pointers into the array become invalid after any push that reallocates; keep indexes instead.

Next: Structures, where you'll learn properly how to define your own record types like IntVec and Point.