A dynamic array is an array that grows and shrinks at runtime. It wraps a fixed-size buffer with a length and a capacity field; when the buffer fills up, a new larger buffer is allocated and the existing elements are copied over. Average-case insertion stays O(1) despite the periodic reallocation.
typedef struct {
int *array;
size_t capacity; // total slots available
size_t length; // slots currently used
} Array;length is how many elements you have. capacity is how many slots are allocated. length <= capacity always.
Initialization
Allocate an initial buffer and start length at 0:
void initArray(Array *a, int initialSize) {
a->array = (int *) malloc(initialSize * sizeof(int));
a->length = 0;
a->capacity = initialSize;
}The initial size is a tunable parameter. Common defaults: 8, 16. Too small → too many early reallocations; too large → wasted memory if the array stays small.
Append (the common operation)
void addToArray(Array *a, int element) {
if (a->length == a->capacity) {
a->capacity *= 2;
a->array = (int *) realloc(a->array, a->capacity * sizeof(int));
}
a->array[a->length++] = element;
}The key trick: when full, double the capacity with realloc. Then add the new element.
realloc either grows the existing buffer in place (if there’s free space adjacent) or allocates a new buffer, copies the old contents, and frees the old buffer. From the caller’s perspective, the operation is transparent — the data survives.
Why doubling?
Doubling the capacity means each element ends up being copied a constant number of times across the lifetime of the array. The first element is copied at every reallocation: 1, 2, 4, 8, …, n times. But the second element only at half of those, the fourth at a quarter, etc. The total work for inserts is , giving amortized O(1) insertion.
If you grew by adding a constant (say, 10 each time), each reallocation would copy more elements, and the total work for inserts would be O(n²). Doubling is what makes dynamic arrays fast.
Insert at index (middle insertion)
bool insertAt(Array *a, size_t index, int value) {
if (index > a->length) return false;
if (a->length == a->capacity) {
a->capacity *= 2;
a->array = realloc(a->array, a->capacity * sizeof(int));
}
memmove(&a->array[index + 1], // destination
&a->array[index], // source
(a->length - index) * sizeof(int));
a->array[index] = value;
a->length++;
return true;
}Shift every element from index onward one slot to the right (using memmove, which handles overlapping memory regions safely), then write the new value at index. O(n) — proportional to how many elements move.
Delete from middle
bool deleteAt(Array *a, size_t index) {
if (index >= a->length) return false;
a->length--;
memmove(&a->array[index],
&a->array[index + 1],
(a->length - index) * sizeof(int));
if (a->length * 4 <= a->capacity) {
a->capacity /= 2;
a->array = realloc(a->array, a->capacity * sizeof(int));
}
return true;
}Shift everything from index+1 onward one slot to the left. Optionally shrink when length drops below 1/4 of capacity to release memory.
The 1/4 threshold (rather than 1/2) prevents thrashing — repeated alternating insertions and deletions near the threshold would otherwise cause repeated realloc grow/shrink cycles.
Free
void freeArray(Array *a) {
free(a->array);
a->array = NULL;
a->capacity = a->length = 0;
}Releases the heap buffer and resets the bookkeeping.
Trade-offs vs linked lists
| Operation | Dynamic array | Linked list |
|---|---|---|
| Indexed access | O(1) | O(n) |
| Append (amortized) | O(1) | O(1) with tail pointer |
| Insert at front | O(n) | O(1) |
| Delete from middle (have pointer) | O(n) | O(1) for doubly linked |
| Memory per element | 1 int | 1 int + 1-2 pointers |
| Cache performance | Excellent (contiguous) | Poor (scattered) |
Dynamic arrays win for indexed access and cache friendliness; linked lists win for cheap front insertion and arbitrary mid-list operations. For most practical use cases, dynamic arrays are the default choice — random access matters more than the linked list’s O(1) front insertion in real workloads.
std::vector in C++, ArrayList in Java, list in Python — all are dynamic arrays under the hood.