Dynamic arrays are one of the most fundamental and versatile data structures in C programming. Unlike static arrays with fixed sizes determined at compile time, dynamic arrays can grow and shrink during runtime, adapting to the needs of your program. This comprehensive guide explores everything from basic allocation to advanced resizing strategies and implementation patterns.
What are Dynamic Arrays?
A dynamic array is an array whose size can be changed at runtime. It combines the contiguous memory layout of static arrays with the flexibility of dynamic memory allocation. The core idea is simple: allocate a block of memory on the heap, track its current size and capacity, and reallocate when more space is needed.
Static Array: Dynamic Array: +-----+-----+-----+ +-----+-----+-----+-----+-----+ (capacity) | 0 | 1 | 2 | | 0 | 1 | 2 | | | +-----+-----+-----+ +-----+-----+-----+-----+-----+ Size: 3 (fixed) Size: 3, Capacity: 5 (can grow)
Basic Dynamic Array Operations
1. Simple Dynamic Array Structure
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int *data; // Pointer to array data
size_t size; // Current number of elements
size_t capacity; // Maximum elements before resize
} DynamicArray;
// Initialize a dynamic array
DynamicArray* da_create(size_t initial_capacity) {
DynamicArray *arr = (DynamicArray*)malloc(sizeof(DynamicArray));
if (arr == NULL) {
fprintf(stderr, "Memory allocation failed\n");
return NULL;
}
arr->data = (int*)malloc(initial_capacity * sizeof(int));
if (arr->data == NULL) {
free(arr);
fprintf(stderr, "Memory allocation failed\n");
return NULL;
}
arr->size = 0;
arr->capacity = initial_capacity;
return arr;
}
// Free the dynamic array
void da_destroy(DynamicArray *arr) {
if (arr) {
free(arr->data);
free(arr);
}
}
2. Adding Elements and Resizing
// Resize the array (internal function)
static int da_resize(DynamicArray *arr, size_t new_capacity) {
int *new_data = (int*)realloc(arr->data, new_capacity * sizeof(int));
if (new_data == NULL) {
return -1; // Allocation failed
}
arr->data = new_data;
arr->capacity = new_capacity;
return 0;
}
// Add element at the end
int da_push_back(DynamicArray *arr, int value) {
if (arr->size >= arr->capacity) {
// Double the capacity
size_t new_capacity = arr->capacity * 2;
if (da_resize(arr, new_capacity) != 0) {
return -1;
}
printf("Resized: %zu -> %zu\n", arr->capacity / 2, arr->capacity);
}
arr->data[arr->size++] = value;
return 0;
}
// Insert at specific index
int da_insert_at(DynamicArray *arr, size_t index, int value) {
if (index > arr->size) {
return -1; // Invalid index
}
// Ensure capacity
if (arr->size >= arr->capacity) {
size_t new_capacity = arr->capacity * 2;
if (da_resize(arr, new_capacity) != 0) {
return -1;
}
}
// Shift elements to the right
for (size_t i = arr->size; i > index; i--) {
arr->data[i] = arr->data[i - 1];
}
arr->data[index] = value;
arr->size++;
return 0;
}
3. Removing Elements
// Remove last element
int da_pop_back(DynamicArray *arr) {
if (arr->size == 0) {
return -1; // Array is empty
}
int value = arr->data[--arr->size];
// Optional: Shrink if size is too small relative to capacity
if (arr->size > 0 && arr->size <= arr->capacity / 4) {
size_t new_capacity = arr->capacity / 2;
if (new_capacity < 4) new_capacity = 4;
da_resize(arr, new_capacity);
printf("Shrunk: %zu -> %zu\n", arr->capacity * 2, arr->capacity);
}
return value;
}
// Remove element at index
int da_remove_at(DynamicArray *arr, size_t index) {
if (index >= arr->size) {
return -1;
}
int value = arr->data[index];
// Shift elements left
for (size_t i = index; i < arr->size - 1; i++) {
arr->data[i] = arr->data[i + 1];
}
arr->size--;
// Shrink if necessary
if (arr->size > 0 && arr->size <= arr->capacity / 4) {
size_t new_capacity = arr->capacity / 2;
if (new_capacity < 4) new_capacity = 4;
da_resize(arr, new_capacity);
}
return value;
}
4. Access and Utility Functions
// Get element at index
int da_get(DynamicArray *arr, size_t index) {
if (index >= arr->size) {
fprintf(stderr, "Index out of bounds\n");
exit(1);
}
return arr->data[index];
}
// Set element at index
void da_set(DynamicArray *arr, size_t index, int value) {
if (index >= arr->size) {
fprintf(stderr, "Index out of bounds\n");
return;
}
arr->data[index] = value;
}
// Get size
size_t da_size(DynamicArray *arr) {
return arr->size;
}
// Get capacity
size_t da_capacity(DynamicArray *arr) {
return arr->capacity;
}
// Check if empty
int da_empty(DynamicArray *arr) {
return arr->size == 0;
}
// Clear all elements
void da_clear(DynamicArray *arr) {
arr->size = 0;
}
// Print array
void da_print(DynamicArray *arr) {
printf("[");
for (size_t i = 0; i < arr->size; i++) {
printf("%d", arr->data[i]);
if (i < arr->size - 1) printf(", ");
}
printf("] (size=%zu, capacity=%zu)\n", arr->size, arr->capacity);
}
Generic Dynamic Array (Using Void Pointers)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
void *data; // Pointer to array data
size_t elem_size; // Size of each element
size_t size; // Current number of elements
size_t capacity; // Maximum elements before resize
} GenericArray;
// Create a generic array
GenericArray* ga_create(size_t elem_size, size_t initial_capacity) {
GenericArray *arr = (GenericArray*)malloc(sizeof(GenericArray));
if (arr == NULL) return NULL;
arr->data = malloc(initial_capacity * elem_size);
if (arr->data == NULL) {
free(arr);
return NULL;
}
arr->elem_size = elem_size;
arr->size = 0;
arr->capacity = initial_capacity;
return arr;
}
// Destroy generic array
void ga_destroy(GenericArray *arr) {
if (arr) {
free(arr->data);
free(arr);
}
}
// Resize internal
static int ga_resize(GenericArray *arr, size_t new_capacity) {
void *new_data = realloc(arr->data, new_capacity * arr->elem_size);
if (new_data == NULL) return -1;
arr->data = new_data;
arr->capacity = new_capacity;
return 0;
}
// Add element at end
int ga_push_back(GenericArray *arr, const void *value) {
if (arr->size >= arr->capacity) {
if (ga_resize(arr, arr->capacity * 2) != 0) return -1;
}
void *dest = (char*)arr->data + arr->size * arr->elem_size;
memcpy(dest, value, arr->elem_size);
arr->size++;
return 0;
}
// Get element at index
void* ga_get(GenericArray *arr, size_t index) {
if (index >= arr->size) return NULL;
return (char*)arr->data + index * arr->elem_size;
}
// Remove element at index
int ga_remove_at(GenericArray *arr, size_t index) {
if (index >= arr->size) return -1;
size_t offset = index * arr->elem_size;
size_t next_offset = (index + 1) * arr->elem_size;
size_t bytes_to_move = (arr->size - index - 1) * arr->elem_size;
memmove((char*)arr->data + offset,
(char*)arr->data + next_offset,
bytes_to_move);
arr->size--;
// Shrink if needed
if (arr->size > 0 && arr->size <= arr->capacity / 4) {
size_t new_capacity = arr->capacity / 2;
if (new_capacity < 4) new_capacity = 4;
ga_resize(arr, new_capacity);
}
return 0;
}
// Example usage
void generic_array_example() {
GenericArray *int_arr = ga_create(sizeof(int), 4);
GenericArray *str_arr = ga_create(sizeof(char*), 4);
// Store integers
for (int i = 0; i < 10; i++) {
ga_push_back(int_arr, &i);
}
// Retrieve integers
printf("Integers: ");
for (size_t i = 0; i < int_arr->size; i++) {
int *val = (int*)ga_get(int_arr, i);
printf("%d ", *val);
}
printf("\n");
// Store strings (pointers)
char *words[] = {"Hello", "World", "Dynamic", "Array"};
for (int i = 0; i < 4; i++) {
ga_push_back(str_arr, &words[i]);
}
// Retrieve strings
printf("Strings: ");
for (size_t i = 0; i < str_arr->size; i++) {
char **str = (char**)ga_get(str_arr, i);
printf("%s ", *str);
}
printf("\n");
ga_destroy(int_arr);
ga_destroy(str_arr);
}
Macro-Based Generic Dynamic Array
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Macro to define a dynamic array type
#define DEFINE_DYNAMIC_ARRAY(type, name) \
typedef struct { \
type *data; \
size_t size; \
size_t capacity; \
} name; \
\
name* name##_create(size_t initial_capacity) { \
name *arr = (name*)malloc(sizeof(name)); \
if (!arr) return NULL; \
arr->data = (type*)malloc(initial_capacity * sizeof(type)); \
if (!arr->data) { free(arr); return NULL; } \
arr->size = 0; \
arr->capacity = initial_capacity; \
return arr; \
} \
\
void name##_destroy(name *arr) { \
if (arr) { free(arr->data); free(arr); } \
} \
\
int name##_push_back(name *arr, type value) { \
if (arr->size >= arr->capacity) { \
type *new_data = (type*)realloc(arr->data, \
arr->capacity * 2 * sizeof(type)); \
if (!new_data) return -1; \
arr->data = new_data; \
arr->capacity *= 2; \
} \
arr->data[arr->size++] = value; \
return 0; \
} \
\
type name##_get(name *arr, size_t index) { \
return arr->data[index]; \
}
// Use the macro to create integer and double arrays
DEFINE_DYNAMIC_ARRAY(int, IntArray)
DEFINE_DYNAMIC_ARRAY(double, DoubleArray)
void macro_example() {
IntArray *int_arr = IntArray_create(4);
DoubleArray *dbl_arr = DoubleArray_create(4);
for (int i = 0; i < 10; i++) {
IntArray_push_back(int_arr, i * 10);
DoubleArray_push_back(dbl_arr, i * 1.5);
}
printf("Integers: ");
for (size_t i = 0; i < int_arr->size; i++) {
printf("%d ", IntArray_get(int_arr, i));
}
printf("\n");
printf("Doubles: ");
for (size_t i = 0; i < dbl_arr->size; i++) {
printf("%.1f ", DoubleArray_get(dbl_arr, i));
}
printf("\n");
IntArray_destroy(int_arr);
DoubleArray_destroy(dbl_arr);
}
Advanced Resizing Strategies
1. Different Growth Factors
typedef struct {
int *data;
size_t size;
size_t capacity;
float growth_factor; // 1.5, 2.0, etc.
} AdvancedArray;
AdvancedArray* aa_create(size_t initial_capacity, float growth_factor) {
AdvancedArray *arr = (AdvancedArray*)malloc(sizeof(AdvancedArray));
arr->data = (int*)malloc(initial_capacity * sizeof(int));
arr->size = 0;
arr->capacity = initial_capacity;
arr->growth_factor = growth_factor;
return arr;
}
int aa_push_back(AdvancedArray *arr, int value) {
if (arr->size >= arr->capacity) {
size_t new_capacity = (size_t)(arr->capacity * arr->growth_factor);
if (new_capacity <= arr->capacity) new_capacity = arr->capacity + 1;
int *new_data = (int*)realloc(arr->data, new_capacity * sizeof(int));
if (!new_data) return -1;
arr->data = new_data;
arr->capacity = new_capacity;
}
arr->data[arr->size++] = value;
return 0;
}
2. Geometric vs Linear Resizing
// Geometric growth (multiply by factor)
static int grow_geometric(AdvancedArray *arr) {
size_t new_capacity = (size_t)(arr->capacity * arr->growth_factor);
int *new_data = (int*)realloc(arr->data, new_capacity * sizeof(int));
if (!new_data) return -1;
arr->data = new_data;
arr->capacity = new_capacity;
return 0;
}
// Linear growth (add fixed increment)
static int grow_linear(AdvancedArray *arr, size_t increment) {
size_t new_capacity = arr->capacity + increment;
int *new_data = (int*)realloc(arr->data, new_capacity * sizeof(int));
if (!new_data) return -1;
arr->data = new_data;
arr->capacity = new_capacity;
return 0;
}
// Hybrid: geometric up to a point, then linear
static int grow_hybrid(AdvancedArray *arr, size_t threshold) {
size_t new_capacity;
if (arr->capacity < threshold) {
new_capacity = arr->capacity * 2; // Double up to threshold
} else {
new_capacity = arr->capacity + 1024; // Add 1024 after threshold
}
int *new_data = (int*)realloc(arr->data, new_capacity * sizeof(int));
if (!new_data) return -1;
arr->data = new_data;
arr->capacity = new_capacity;
return 0;
}
Memory Management and Optimization
1. Memory Pool Allocation
#include <stddef.h>
typedef struct {
void *pool;
size_t pool_size;
size_t used;
void *current_block;
size_t block_size;
} MemoryPool;
MemoryPool* pool_create(size_t size) {
MemoryPool *pool = malloc(sizeof(MemoryPool));
pool->pool = malloc(size);
pool->pool_size = size;
pool->used = 0;
pool->current_block = pool->pool;
pool->block_size = 0;
return pool;
}
void pool_destroy(MemoryPool *pool) {
if (pool) {
free(pool->pool);
free(pool);
}
}
void* pool_alloc(MemoryPool *pool, size_t size) {
if (pool->used + size > pool->pool_size) {
return NULL; // Out of memory
}
void *ptr = (char*)pool->pool + pool->used;
pool->used += size;
return ptr;
}
void pool_reset(MemoryPool *pool) {
pool->used = 0;
}
// Dynamic array using memory pool
typedef struct {
int *data;
size_t size;
size_t capacity;
MemoryPool *pool;
} PoolArray;
PoolArray* pa_create(MemoryPool *pool, size_t initial_capacity) {
PoolArray *arr = (PoolArray*)pool_alloc(pool, sizeof(PoolArray));
arr->data = (int*)pool_alloc(pool, initial_capacity * sizeof(int));
arr->size = 0;
arr->capacity = initial_capacity;
arr->pool = pool;
return arr;
}
2. Cache-Friendly Array Layout
// Cache-aware dynamic array (padding to avoid false sharing)
typedef struct {
int data[64]; // Cache line sized block
size_t count;
struct Block *next;
} Block;
typedef struct {
Block *head;
Block *tail;
size_t size;
} BlockArray;
BlockArray* ba_create() {
BlockArray *arr = malloc(sizeof(BlockArray));
arr->head = arr->tail = NULL;
arr->size = 0;
return arr;
}
int ba_push_back(BlockArray *arr, int value) {
if (arr->tail == NULL || arr->tail->count >= 64) {
Block *new_block = malloc(sizeof(Block));
new_block->count = 0;
new_block->next = NULL;
if (arr->tail) {
arr->tail->next = new_block;
} else {
arr->head = new_block;
}
arr->tail = new_block;
}
arr->tail->data[arr->tail->count++] = value;
arr->size++;
return 0;
}
int ba_get(BlockArray *arr, size_t index) {
Block *block = arr->head;
while (index >= 64) {
index -= 64;
block = block->next;
if (!block) return -1;
}
return block->data[index];
}
Sorting and Searching
#include <stdlib.h>
// Sort the dynamic array
void da_sort(DynamicArray *arr, int (*compare)(const void*, const void*)) {
qsort(arr->data, arr->size, sizeof(int), compare);
}
// Binary search on sorted array
int da_binary_search(DynamicArray *arr, int target) {
size_t left = 0;
size_t right = arr->size;
while (left < right) {
size_t mid = left + (right - left) / 2;
if (arr->data[mid] == target) {
return (int)mid;
} else if (arr->data[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return -1;
}
// Filter elements
DynamicArray* da_filter(DynamicArray *arr, int (*predicate)(int)) {
DynamicArray *result = da_create(arr->capacity);
for (size_t i = 0; i < arr->size; i++) {
if (predicate(arr->data[i])) {
da_push_back(result, arr->data[i]);
}
}
return result;
}
// Map transformation
DynamicArray* da_map(DynamicArray *arr, int (*transform)(int)) {
DynamicArray *result = da_create(arr->capacity);
for (size_t i = 0; i < arr->size; i++) {
da_push_back(result, transform(arr->data[i]));
}
return result;
}
Complete Example: Vector Implementation
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VECTOR_INIT_CAPACITY 8
#define VECTOR_GROWTH_FACTOR 2
#define VECTOR_SHRINK_THRESHOLD 4
typedef struct {
void *data;
size_t elem_size;
size_t size;
size_t capacity;
} Vector;
Vector* vector_create(size_t elem_size, size_t initial_capacity) {
if (initial_capacity == 0) initial_capacity = VECTOR_INIT_CAPACITY;
Vector *vec = (Vector*)malloc(sizeof(Vector));
if (!vec) return NULL;
vec->data = malloc(initial_capacity * elem_size);
if (!vec->data) {
free(vec);
return NULL;
}
vec->elem_size = elem_size;
vec->size = 0;
vec->capacity = initial_capacity;
return vec;
}
void vector_destroy(Vector *vec) {
if (vec) {
free(vec->data);
free(vec);
}
}
int vector_reserve(Vector *vec, size_t new_capacity) {
if (new_capacity <= vec->capacity) return 0;
void *new_data = realloc(vec->data, new_capacity * vec->elem_size);
if (!new_data) return -1;
vec->data = new_data;
vec->capacity = new_capacity;
return 0;
}
int vector_shrink_to_fit(Vector *vec) {
if (vec->size == vec->capacity) return 0;
void *new_data = realloc(vec->data, vec->size * vec->elem_size);
if (!new_data && vec->size > 0) return -1;
vec->data = new_data;
vec->capacity = vec->size;
return 0;
}
int vector_push_back(Vector *vec, const void *value) {
if (vec->size >= vec->capacity) {
if (vector_reserve(vec, vec->capacity * VECTOR_GROWTH_FACTOR) != 0) {
return -1;
}
}
void *dest = (char*)vec->data + vec->size * vec->elem_size;
memcpy(dest, value, vec->elem_size);
vec->size++;
return 0;
}
int vector_pop_back(Vector *vec, void *out) {
if (vec->size == 0) return -1;
vec->size--;
void *src = (char*)vec->data + vec->size * vec->elem_size;
if (out) memcpy(out, src, vec->elem_size);
// Shrink if necessary
if (vec->size > 0 && vec->size <= vec->capacity / VECTOR_SHRINK_THRESHOLD) {
size_t new_capacity = vec->capacity / 2;
if (new_capacity < VECTOR_INIT_CAPACITY) {
new_capacity = VECTOR_INIT_CAPACITY;
}
vector_reserve(vec, new_capacity);
}
return 0;
}
void* vector_at(Vector *vec, size_t index) {
if (index >= vec->size) return NULL;
return (char*)vec->data + index * vec->elem_size;
}
int vector_insert_at(Vector *vec, size_t index, const void *value) {
if (index > vec->size) return -1;
if (vec->size >= vec->capacity) {
if (vector_reserve(vec, vec->capacity * VECTOR_GROWTH_FACTOR) != 0) {
return -1;
}
}
size_t offset = index * vec->elem_size;
size_t bytes_to_move = (vec->size - index) * vec->elem_size;
memmove((char*)vec->data + offset + vec->elem_size,
(char*)vec->data + offset,
bytes_to_move);
memcpy((char*)vec->data + offset, value, vec->elem_size);
vec->size++;
return 0;
}
int vector_erase_at(Vector *vec, size_t index) {
if (index >= vec->size) return -1;
size_t offset = index * vec->elem_size;
size_t bytes_to_move = (vec->size - index - 1) * vec->elem_size;
memmove((char*)vec->data + offset,
(char*)vec->data + offset + vec->elem_size,
bytes_to_move);
vec->size--;
// Shrink if necessary
if (vec->size > 0 && vec->size <= vec->capacity / VECTOR_SHRINK_THRESHOLD) {
size_t new_capacity = vec->capacity / 2;
if (new_capacity < VECTOR_INIT_CAPACITY) {
new_capacity = VECTOR_INIT_CAPACITY;
}
vector_reserve(vec, new_capacity);
}
return 0;
}
void vector_clear(Vector *vec) {
vec->size = 0;
}
size_t vector_size(Vector *vec) {
return vec->size;
}
size_t vector_capacity(Vector *vec) {
return vec->capacity;
}
int vector_empty(Vector *vec) {
return vec->size == 0;
}
// Example usage
int main() {
Vector *vec = vector_create(sizeof(int), 4);
printf("Adding elements...\n");
for (int i = 0; i < 20; i++) {
vector_push_back(vec, &i);
printf(" Added %d: size=%zu, capacity=%zu\n",
i, vec->size, vec->capacity);
}
printf("\nElements: ");
for (size_t i = 0; i < vec->size; i++) {
int *val = (int*)vector_at(vec, i);
printf("%d ", *val);
}
printf("\n");
printf("\nRemoving elements...\n");
while (!vector_empty(vec)) {
int val;
vector_pop_back(vec, &val);
printf(" Removed %d: size=%zu, capacity=%zu\n",
val, vec->size, vec->capacity);
}
printf("\nShrinking to fit...\n");
vector_shrink_to_fit(vec);
printf(" size=%zu, capacity=%zu\n", vec->size, vec->capacity);
vector_destroy(vec);
return 0;
}
Performance Considerations
#include <time.h>
void benchmark_dynamic_array() {
const size_t OPERATIONS = 10000000;
// Test push_back performance
DynamicArray *arr = da_create(64);
clock_t start = clock();
for (size_t i = 0; i < OPERATIONS; i++) {
da_push_back(arr, (int)i);
}
clock_t end = clock();
double time = (double)(end - start) / CLOCKS_PER_SEC;
printf("Push_back %zu elements: %.3f seconds\n", OPERATIONS, time);
printf(" Final capacity: %zu\n", arr->capacity);
printf(" Memory usage: %.2f MB\n",
arr->capacity * sizeof(int) / (1024.0 * 1024.0));
da_destroy(arr);
}
Best Practices Summary
- Choose appropriate growth factor: 2.0 is simple, 1.5 is more memory-efficient
- Shrink when appropriate: Consider shrinking when size < capacity/4
- Use
reallocefficiently: Let the library handle memory movement - Consider alignment: For generic arrays, ensure proper alignment
- Provide capacity management: Offer
reserve()andshrink_to_fit() - Handle allocation failures: Always check return values
- Document complexity: Users need to know when resizing occurs
- Consider memory pools: For many small allocations
- Use
memcpy/memmove: For moving blocks of data - Profile before optimizing: Different use cases need different strategies
Conclusion
Dynamic arrays are a cornerstone of efficient C programming. They combine the speed of contiguous memory with the flexibility of dynamic sizing. By understanding the implementation details—resizing strategies, memory management, and access patterns—you can create high-performance, memory-efficient data structures that scale from small collections to large datasets.
Whether you need a simple integer array or a generic container for complex data types, the patterns in this guide provide a solid foundation. Remember that the best implementation depends on your specific use case: growth patterns, element sizes, and access patterns all influence the optimal design. With these tools in your arsenal, you can build C programs that are both flexible and fast.