A dynamic array is a resizable sequence backed by a heap-allocated Array. It provides O(1) indexed access like a fixed array, but grows automatically when capacity is exceeded. When the backing array is full and a new element is appended, the implementation allocates a larger array (typically 2×), copies all elements over, and frees the old allocation. The amortised cost of appending is O(1) because the copying work is spread across all the inserts that preceded the resize.

struct vec {
    int   *data;
    size_t len;
    size_t cap;
};
 
void push(struct vec *v, int val) {
    if (v->len == v->cap) {
        v->cap  = v->cap ? v->cap * 2 : 4;
        v->data = realloc(v->data, v->cap * sizeof *v->data);
    }
    v->data[v->len++] = val;
}

The 2× growth factor keeps the total number of copies linear: each element is copied at most O(log n) times across all resizes, giving O(1) amortised per push. A smaller factor (e.g. 1.5×) wastes less memory at the cost of more frequent copies; a larger factor wastes more memory but copies less often. The standard libraries of most languages use values between 1.5 and 2.

realloc in C attempts to extend the allocation in place before copying, which avoids a copy in many cases. Inserting or deleting at a position other than the end shifts subsequent elements and costs O(n).