Dynamic Arrays in C

Table of Contents

1. •Introduction
2. •Understanding Dynamic Arrays
3. •Implementing One-Dimensional Dynamic Arrays
4. •Implementing Two-Dimensional Dynamic Arrays
5. •Dynamic Array ADT (Abstract Data Type)
6. •Resizable Array Implementation
7. •Performance Analysis
8. •Memory Management Strategies
9. •Common Patterns and Use Cases
10. •Best Practices
11. •Summary

---

Introduction

A dynamic array (also known as a resizable array, growable array, or vector) is a data structure that can change its size during program execution. Unlike static arrays with fixed compile-time sizes, dynamic arrays can grow or shrink as needed.

Why Dynamic Arrays?

/* Static array - size must be known at compile time */
int static_arr[100];  /* Always 100 elements, potentially wasteful */

/* VLA (Variable Length Array) - stack allocated, can't resize */
int n = get_size();
int vla[n];  /* Size set at runtime, but can't change */

/* Dynamic array - heap allocated, can resize */
int *dynamic_arr = malloc(n * sizeof(int));
/* ... later ... */
dynamic_arr = realloc(dynamic_arr, m * sizeof(int));  /* Resize! */

Advantages of Dynamic Arrays

1. •Flexible size: Allocate exactly what you need
2. •Resizable: Can grow or shrink at runtime
3. •Heap allocation: Not limited by stack size
4. •Lifetime control: Memory persists beyond function scope

Disadvantages

1. •Manual management: Must explicitly allocate and free
2. •Overhead: Memory allocation has performance cost
3. •Fragmentation: Many small allocations can fragment heap
4. •Error-prone: Risk of memory leaks, use-after-free

---

Understanding Dynamic Arrays

Memory Layout Comparison

Static Array:
┌──────────────────────────────────────────────────────────┐
│ STACK                                                     │
│  ┌─────┬─────┬─────┬─────┬─────┐                         │
│  │  0  │  1  │  2  │  3  │  4  │  int arr[5];            │
│  └─────┴─────┴─────┴─────┴─────┘                         │
│  Fixed size, contiguous                                   │
└──────────────────────────────────────────────────────────┘

Dynamic Array:
┌──────────────────┐  ┌──────────────────────────────────────┐
│ STACK            │  │ HEAP                                  │
│  ┌────────┐      │  │  ┌─────┬─────┬─────┬─────┬─────┐     │
│  │  ptr ──┼──────┼──┼──│  0  │  1  │  2  │  3  │  4  │     │
│  └────────┘      │  │  └─────┴─────┴─────┴─────┴─────┘     │
│  Pointer         │  │  Can be reallocated                   │
└──────────────────┘  └──────────────────────────────────────┘

Key Concepts

1. •Capacity: Total allocated space
2. •Size/Length: Number of elements currently used
3. •Growth factor: How much to expand when full (typically 1.5x or 2x)
4. •Shrink threshold: When to reduce capacity (e.g., 25% utilization)

typedef struct {
    int *data;      /* Pointer to array data */
    size_t size;    /* Number of elements in use */
    size_t capacity;/* Total allocated elements */
} DynamicArray;

/*
 * size = 5, capacity = 8
 * ┌───┬───┬───┬───┬───┬───┬───┬───┐
 * │ A │ B │ C │ D │ E │   │   │   │
 * └───┴───┴───┴───┴───┴───┴───┴───┘
 *   0   1   2   3   4   5   6   7
 *                   ↑           ↑
 *                 size      capacity
 */

---

Implementing One-Dimensional Dynamic Arrays

Basic Allocation and Usage

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Create a dynamic array of integers */
int *create_int_array(size_t size) {
    int *arr = malloc(size * sizeof(int));
    if (arr == NULL) {
        perror("malloc");
        return NULL;
    }
    return arr;
}

/* Create and initialize to zero */
int *create_int_array_zeroed(size_t size) {
    return calloc(size, sizeof(int));
}

/* Resize array (growing or shrinking) */
int *resize_int_array(int *arr, size_t old_size, size_t new_size) {
    int *new_arr = realloc(arr, new_size * sizeof(int));
    if (new_arr == NULL && new_size > 0) {
        return NULL;  /* Original arr still valid */
    }
    return new_arr;
}

/* Free the array */
void destroy_int_array(int *arr) {
    free(arr);
}

/* Example usage */
int main(void) {
    size_t size = 5;

    /* Create */
    int *arr = create_int_array(size);
    if (!arr) return 1;

    /* Initialize */
    for (size_t i = 0; i < size; i++) {
        arr[i] = (int)(i * 10);
    }

    /* Print */
    printf("Original array: ");
    for (size_t i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    /* Resize to larger */
    size_t new_size = 10;
    int *temp = resize_int_array(arr, size, new_size);
    if (temp) {
        arr = temp;
        /* Initialize new elements */
        for (size_t i = size; i < new_size; i++) {
            arr[i] = (int)(i * 10);
        }
        size = new_size;
    }

    /* Print resized */
    printf("Resized array: ");
    for (size_t i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    /* Cleanup */
    destroy_int_array(arr);
    return 0;
}

Generic Dynamic Array with Macros

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Macro to create type-specific dynamic array functions */
#define DEFINE_DYNAMIC_ARRAY(type, name)                           \
    type *name##_create(size_t size) {                             \
        return malloc(size * sizeof(type));                        \
    }                                                              \
                                                                   \
    type *name##_resize(type *arr, size_t new_size) {              \
        return realloc(arr, new_size * sizeof(type));              \
    }                                                              \
                                                                   \
    void name##_destroy(type *arr) {                               \
        free(arr);                                                 \
    }                                                              \
                                                                   \
    void name##_copy(type *dest, const type *src, size_t n) {      \
        memcpy(dest, src, n * sizeof(type));                       \
    }

/* Generate functions for int arrays */
DEFINE_DYNAMIC_ARRAY(int, int_array)

/* Generate functions for double arrays */
DEFINE_DYNAMIC_ARRAY(double, double_array)

int main(void) {
    /* Use generated int array functions */
    int *ints = int_array_create(10);
    for (int i = 0; i < 10; i++) ints[i] = i;
    int_array_destroy(ints);

    /* Use generated double array functions */
    double *doubles = double_array_create(5);
    for (int i = 0; i < 5; i++) doubles[i] = i * 1.5;
    double_array_destroy(doubles);

    return 0;
}

---

Implementing Two-Dimensional Dynamic Arrays

Method 1: Array of Pointers (Flexible)

#include <stdio.h>
#include <stdlib.h>

/*
 * Memory layout:
 *
 * rows[0] ──→ ┌─────┬─────┬─────┬─────┐
 *             │  0  │  1  │  2  │  3  │
 *             └─────┴─────┴─────┴─────┘
 * rows[1] ──→ ┌─────┬─────┬─────┬─────┐
 *             │  4  │  5  │  6  │  7  │
 *             └─────┴─────┴─────┴─────┘
 * rows[2] ──→ ┌─────┬─────┬─────┬─────┐
 *             │  8  │  9  │ 10  │ 11  │
 *             └─────┴─────┴─────┴─────┘
 */

/* Create 2D array (array of pointers) */
int **create_2d_array(size_t rows, size_t cols) {
    /* Allocate array of row pointers */
    int **arr = malloc(rows * sizeof(int *));
    if (!arr) return NULL;

    /* Allocate each row */
    for (size_t i = 0; i < rows; i++) {
        arr[i] = malloc(cols * sizeof(int));
        if (!arr[i]) {
            /* Cleanup on failure */
            while (i > 0) {
                free(arr[--i]);
            }
            free(arr);
            return NULL;
        }
    }

    return arr;
}

/* Free 2D array */
void destroy_2d_array(int **arr, size_t rows) {
    if (!arr) return;

    for (size_t i = 0; i < rows; i++) {
        free(arr[i]);
    }
    free(arr);
}

/* Example usage */
int main(void) {
    size_t rows = 3, cols = 4;

    int **matrix = create_2d_array(rows, cols);
    if (!matrix) return 1;

    /* Fill matrix */
    int count = 0;
    for (size_t i = 0; i < rows; i++) {
        for (size_t j = 0; j < cols; j++) {
            matrix[i][j] = count++;
        }
    }

    /* Print matrix */
    printf("Matrix:\n");
    for (size_t i = 0; i < rows; i++) {
        for (size_t j = 0; j < cols; j++) {
            printf("%3d ", matrix[i][j]);
        }
        printf("\n");
    }

    destroy_2d_array(matrix, rows);
    return 0;
}

Method 2: Contiguous Memory Block (Cache-Friendly)

#include <stdio.h>
#include <stdlib.h>

/*
 * Memory layout:
 *
 * ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
 * │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │  8  │  9  │ 10  │ 11  │
 * └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
 * ←─── Row 0 ────→ ←─── Row 1 ────→ ←─── Row 2 ────→
 *
 * Access: arr[i * cols + j]
 */

typedef struct {
    int *data;
    size_t rows;
    size_t cols;
} Matrix;

/* Create contiguous 2D array */
Matrix *matrix_create(size_t rows, size_t cols) {
    Matrix *m = malloc(sizeof(Matrix));
    if (!m) return NULL;

    m->data = calloc(rows * cols, sizeof(int));
    if (!m->data) {
        free(m);
        return NULL;
    }

    m->rows = rows;
    m->cols = cols;
    return m;
}

/* Access element */
int *matrix_at(Matrix *m, size_t row, size_t col) {
    if (row >= m->rows || col >= m->cols) {
        return NULL;  /* Bounds check */
    }
    return &m->data[row * m->cols + col];
}

/* Get element value */
int matrix_get(Matrix *m, size_t row, size_t col) {
    int *ptr = matrix_at(m, row, col);
    return ptr ? *ptr : 0;
}

/* Set element value */
void matrix_set(Matrix *m, size_t row, size_t col, int value) {
    int *ptr = matrix_at(m, row, col);
    if (ptr) *ptr = value;
}

/* Resize matrix (preserves data where possible) */
Matrix *matrix_resize(Matrix *m, size_t new_rows, size_t new_cols) {
    Matrix *new_m = matrix_create(new_rows, new_cols);
    if (!new_m) return NULL;

    /* Copy existing data */
    size_t copy_rows = (m->rows < new_rows) ? m->rows : new_rows;
    size_t copy_cols = (m->cols < new_cols) ? m->cols : new_cols;

    for (size_t i = 0; i < copy_rows; i++) {
        for (size_t j = 0; j < copy_cols; j++) {
            matrix_set(new_m, i, j, matrix_get(m, i, j));
        }
    }

    return new_m;
}

/* Free matrix */
void matrix_destroy(Matrix *m) {
    if (m) {
        free(m->data);
        free(m);
    }
}

/* Print matrix */
void matrix_print(Matrix *m) {
    for (size_t i = 0; i < m->rows; i++) {
        for (size_t j = 0; j < m->cols; j++) {
            printf("%4d ", matrix_get(m, i, j));
        }
        printf("\n");
    }
}

int main(void) {
    Matrix *m = matrix_create(3, 4);
    if (!m) return 1;

    /* Fill with values */
    int count = 1;
    for (size_t i = 0; i < m->rows; i++) {
        for (size_t j = 0; j < m->cols; j++) {
            matrix_set(m, i, j, count++);
        }
    }

    printf("Original 3x4 matrix:\n");
    matrix_print(m);

    /* Resize to 4x5 */
    Matrix *resized = matrix_resize(m, 4, 5);
    if (resized) {
        matrix_destroy(m);
        m = resized;

        printf("\nResized 4x5 matrix:\n");
        matrix_print(m);
    }

    matrix_destroy(m);
    return 0;
}

Method 3: Single Allocation with Row Pointers

#include <stdio.h>
#include <stdlib.h>

/*
 * Memory layout (single allocation):
 *
 * ┌──────────┬──────────┬──────────┬─────────────────────────────┐
 * │ rows[0]  │ rows[1]  │ rows[2]  │  0  1  2  3  4  5  6  7 ... │
 * │    ↓     │    ↓     │    ↓     │                             │
 * └────┼─────┴────┼─────┴────┼─────┴─────────────────────────────┘
 *      │          │          │          ↑
 *      └──────────┴──────────┴──────────┘
 *      Points into the data area
 */

int **create_2d_contiguous(size_t rows, size_t cols) {
    /* Single allocation for pointers + data */
    int **arr = malloc(rows * sizeof(int *) + rows * cols * sizeof(int));
    if (!arr) return NULL;

    /* Data starts after pointer array */
    int *data = (int *)(arr + rows);

    /* Set up row pointers */
    for (size_t i = 0; i < rows; i++) {
        arr[i] = data + i * cols;
    }

    return arr;
}

void destroy_2d_contiguous(int **arr) {
    free(arr);  /* Single free - everything allocated together */
}

int main(void) {
    size_t rows = 3, cols = 4;

    int **matrix = create_2d_contiguous(rows, cols);
    if (!matrix) return 1;

    /* Use like normal 2D array */
    int count = 0;
    for (size_t i = 0; i < rows; i++) {
        for (size_t j = 0; j < cols; j++) {
            matrix[i][j] = count++;
        }
    }

    /* Print */
    for (size_t i = 0; i < rows; i++) {
        for (size_t j = 0; j < cols; j++) {
            printf("%3d ", matrix[i][j]);
        }
        printf("\n");
    }

    destroy_2d_contiguous(matrix);
    return 0;
}

---

Dynamic Array ADT

Complete Implementation

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define DYNARRAY_INITIAL_CAPACITY 8
#define DYNARRAY_GROWTH_FACTOR 2
#define DYNARRAY_SHRINK_THRESHOLD 4  /* Shrink if size < capacity/4 */

typedef struct {
    void *data;          /* Array data */
    size_t size;         /* Number of elements */
    size_t capacity;     /* Allocated capacity */
    size_t element_size; /* Size of each element */
} DynArray;

/* Error codes */
typedef enum {
    DYNARRAY_OK = 0,
    DYNARRAY_ALLOC_FAIL = -1,
    DYNARRAY_INDEX_OUT_OF_BOUNDS = -2,
    DYNARRAY_EMPTY = -3
} DynArrayError;

/* Create a new dynamic array */
DynArray *dynarray_create(size_t element_size) {
    DynArray *arr = malloc(sizeof(DynArray));
    if (!arr) return NULL;

    arr->data = calloc(DYNARRAY_INITIAL_CAPACITY, element_size);
    if (!arr->data) {
        free(arr);
        return NULL;
    }

    arr->size = 0;
    arr->capacity = DYNARRAY_INITIAL_CAPACITY;
    arr->element_size = element_size;
    return arr;
}

/* Create with initial capacity */
DynArray *dynarray_create_with_capacity(size_t element_size, size_t capacity) {
    DynArray *arr = malloc(sizeof(DynArray));
    if (!arr) return NULL;

    size_t initial_cap = capacity > 0 ? capacity : 1;
    arr->data = calloc(initial_cap, element_size);
    if (!arr->data) {
        free(arr);
        return NULL;
    }

    arr->size = 0;
    arr->capacity = initial_cap;
    arr->element_size = element_size;
    return arr;
}

/* Destroy the array */
void dynarray_destroy(DynArray *arr) {
    if (arr) {
        free(arr->data);
        free(arr);
    }
}

/* Get pointer to element at index */
void *dynarray_get(DynArray *arr, size_t index) {
    if (index >= arr->size) return NULL;
    return (char *)arr->data + index * arr->element_size;
}

/* Ensure capacity for n elements */
static int dynarray_ensure_capacity(DynArray *arr, size_t min_capacity) {
    if (min_capacity <= arr->capacity) return DYNARRAY_OK;

    size_t new_capacity = arr->capacity;
    while (new_capacity < min_capacity) {
        new_capacity *= DYNARRAY_GROWTH_FACTOR;
    }

    void *new_data = realloc(arr->data, new_capacity * arr->element_size);
    if (!new_data) return DYNARRAY_ALLOC_FAIL;

    arr->data = new_data;
    arr->capacity = new_capacity;
    return DYNARRAY_OK;
}

/* Try to shrink if appropriate */
static void dynarray_maybe_shrink(DynArray *arr) {
    if (arr->capacity <= DYNARRAY_INITIAL_CAPACITY) return;
    if (arr->size >= arr->capacity / DYNARRAY_SHRINK_THRESHOLD) return;

    size_t new_capacity = arr->capacity / DYNARRAY_GROWTH_FACTOR;
    if (new_capacity < DYNARRAY_INITIAL_CAPACITY) {
        new_capacity = DYNARRAY_INITIAL_CAPACITY;
    }

    void *new_data = realloc(arr->data, new_capacity * arr->element_size);
    if (new_data) {
        arr->data = new_data;
        arr->capacity = new_capacity;
    }
    /* Ignore shrink failure - not critical */
}

/* Push element to end */
int dynarray_push(DynArray *arr, const void *element) {
    if (dynarray_ensure_capacity(arr, arr->size + 1) != DYNARRAY_OK) {
        return DYNARRAY_ALLOC_FAIL;
    }

    void *dest = (char *)arr->data + arr->size * arr->element_size;
    memcpy(dest, element, arr->element_size);
    arr->size++;
    return DYNARRAY_OK;
}

/* Pop element from end */
int dynarray_pop(DynArray *arr, void *out) {
    if (arr->size == 0) return DYNARRAY_EMPTY;

    arr->size--;
    if (out) {
        void *src = (char *)arr->data + arr->size * arr->element_size;
        memcpy(out, src, arr->element_size);
    }

    dynarray_maybe_shrink(arr);
    return DYNARRAY_OK;
}

/* Set element at index */
int dynarray_set(DynArray *arr, size_t index, const void *element) {
    if (index >= arr->size) return DYNARRAY_INDEX_OUT_OF_BOUNDS;

    void *dest = (char *)arr->data + index * arr->element_size;
    memcpy(dest, element, arr->element_size);
    return DYNARRAY_OK;
}

/* Insert element at index */
int dynarray_insert(DynArray *arr, size_t index, const void *element) {
    if (index > arr->size) return DYNARRAY_INDEX_OUT_OF_BOUNDS;

    if (dynarray_ensure_capacity(arr, arr->size + 1) != DYNARRAY_OK) {
        return DYNARRAY_ALLOC_FAIL;
    }

    /* Shift elements right */
    if (index < arr->size) {
        void *src = (char *)arr->data + index * arr->element_size;
        void *dest = (char *)arr->data + (index + 1) * arr->element_size;
        size_t move_size = (arr->size - index) * arr->element_size;
        memmove(dest, src, move_size);
    }

    /* Insert element */
    void *dest = (char *)arr->data + index * arr->element_size;
    memcpy(dest, element, arr->element_size);
    arr->size++;
    return DYNARRAY_OK;
}

/* Remove element at index */
int dynarray_remove(DynArray *arr, size_t index, void *out) {
    if (index >= arr->size) return DYNARRAY_INDEX_OUT_OF_BOUNDS;

    void *src = (char *)arr->data + index * arr->element_size;

    /* Copy out if requested */
    if (out) {
        memcpy(out, src, arr->element_size);
    }

    /* Shift elements left */
    if (index < arr->size - 1) {
        void *dest = src;
        void *next = (char *)src + arr->element_size;
        size_t move_size = (arr->size - index - 1) * arr->element_size;
        memmove(dest, next, move_size);
    }

    arr->size--;
    dynarray_maybe_shrink(arr);
    return DYNARRAY_OK;
}

/* Get size */
size_t dynarray_size(const DynArray *arr) {
    return arr->size;
}

/* Get capacity */
size_t dynarray_capacity(const DynArray *arr) {
    return arr->capacity;
}

/* Check if empty */
int dynarray_is_empty(const DynArray *arr) {
    return arr->size == 0;
}

/* Clear all elements */
void dynarray_clear(DynArray *arr) {
    arr->size = 0;
    dynarray_maybe_shrink(arr);
}

/* Reserve capacity */
int dynarray_reserve(DynArray *arr, size_t capacity) {
    return dynarray_ensure_capacity(arr, capacity);
}

/* Shrink capacity to size */
int dynarray_shrink_to_fit(DynArray *arr) {
    if (arr->size == 0) {
        void *new_data = realloc(arr->data, arr->element_size);
        if (new_data) {
            arr->data = new_data;
            arr->capacity = 1;
        }
    } else if (arr->size < arr->capacity) {
        void *new_data = realloc(arr->data, arr->size * arr->element_size);
        if (new_data) {
            arr->data = new_data;
            arr->capacity = arr->size;
        }
    }
    return DYNARRAY_OK;
}

/* Example usage */
int main(void) {
    /* Create array for integers */
    DynArray *arr = dynarray_create(sizeof(int));
    if (!arr) {
        fprintf(stderr, "Failed to create array\n");
        return 1;
    }

    /* Push elements */
    for (int i = 0; i < 20; i++) {
        int value = i * 10;
        if (dynarray_push(arr, &value) != DYNARRAY_OK) {
            fprintf(stderr, "Push failed\n");
            dynarray_destroy(arr);
            return 1;
        }
    }

    printf("Array size: %zu, capacity: %zu\n",
           dynarray_size(arr), dynarray_capacity(arr));

    /* Print elements */
    printf("Elements: ");
    for (size_t i = 0; i < dynarray_size(arr); i++) {
        int *ptr = dynarray_get(arr, i);
        if (ptr) printf("%d ", *ptr);
    }
    printf("\n");

    /* Insert at position 5 */
    int insert_val = 999;
    dynarray_insert(arr, 5, &insert_val);
    printf("After inserting 999 at index 5:\n");
    for (size_t i = 0; i < dynarray_size(arr); i++) {
        int *ptr = dynarray_get(arr, i);
        if (ptr) printf("%d ", *ptr);
    }
    printf("\n");

    /* Pop elements */
    int popped;
    while (dynarray_pop(arr, &popped) == DYNARRAY_OK) {
        /* Just removing */
    }

    printf("After popping all: size = %zu\n", dynarray_size(arr));

    dynarray_destroy(arr);
    return 0;
}

---

Resizable Array Implementation

Type-Safe Integer Array

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} IntVector;

/* Constructor */
IntVector *intvec_new(void) {
    IntVector *v = malloc(sizeof(IntVector));
    if (!v) return NULL;

    v->data = malloc(4 * sizeof(int));
    if (!v->data) {
        free(v);
        return NULL;
    }

    v->size = 0;
    v->capacity = 4;
    return v;
}

/* Destructor */
void intvec_free(IntVector *v) {
    if (v) {
        free(v->data);
        free(v);
    }
}

/* Grow helper */
static int intvec_grow(IntVector *v) {
    size_t new_cap = v->capacity * 2;
    int *new_data = realloc(v->data, new_cap * sizeof(int));
    if (!new_data) return -1;

    v->data = new_data;
    v->capacity = new_cap;
    return 0;
}

/* Push back */
int intvec_push(IntVector *v, int value) {
    if (v->size >= v->capacity) {
        if (intvec_grow(v) != 0) return -1;
    }
    v->data[v->size++] = value;
    return 0;
}

/* Pop back */
int intvec_pop(IntVector *v) {
    if (v->size == 0) return 0;  /* Return 0 for empty */
    return v->data[--v->size];
}

/* Access with bounds check */
int *intvec_at(IntVector *v, size_t index) {
    if (index >= v->size) return NULL;
    return &v->data[index];
}

/* Direct access (no bounds check) */
int intvec_get(IntVector *v, size_t index) {
    return v->data[index];
}

/* Set value */
void intvec_set(IntVector *v, size_t index, int value) {
    if (index < v->size) {
        v->data[index] = value;
    }
}

/* Get size */
size_t intvec_size(IntVector *v) {
    return v->size;
}

/* Check if empty */
int intvec_empty(IntVector *v) {
    return v->size == 0;
}

/* Clear */
void intvec_clear(IntVector *v) {
    v->size = 0;
}

/* Find element */
int intvec_find(IntVector *v, int value) {
    for (size_t i = 0; i < v->size; i++) {
        if (v->data[i] == value) return (int)i;
    }
    return -1;
}

/* Print */
void intvec_print(IntVector *v) {
    printf("[");
    for (size_t i = 0; i < v->size; i++) {
        printf("%d", v->data[i]);
        if (i < v->size - 1) printf(", ");
    }
    printf("] (size=%zu, cap=%zu)\n", v->size, v->capacity);
}

int main(void) {
    IntVector *v = intvec_new();
    if (!v) return 1;

    /* Add elements */
    for (int i = 1; i <= 10; i++) {
        intvec_push(v, i * i);
    }

    printf("After adding 10 squares: ");
    intvec_print(v);

    /* Pop some */
    printf("Popped: %d\n", intvec_pop(v));
    printf("Popped: %d\n", intvec_pop(v));

    printf("After popping: ");
    intvec_print(v);

    /* Find */
    int idx = intvec_find(v, 25);
    printf("Index of 25: %d\n", idx);

    /* Modify */
    intvec_set(v, 0, 100);
    printf("After setting [0] to 100: ");
    intvec_print(v);

    intvec_free(v);
    return 0;
}

---

Performance Analysis

Time Complexity

Amortized Analysis of Push

Push operations with doubling:

Capacity: 1 → 2 → 4 → 8 → 16 → 32 → 64 → ...

Copies during reallocation:
- When capacity 1→2:  copy 1 element
- When capacity 2→4:  copy 2 elements
- When capacity 4→8:  copy 4 elements
- When capacity 8→16: copy 8 elements
...

Total copies for n insertions:
1 + 2 + 4 + 8 + ... + n/2 + n = 2n - 1 = O(n)

Amortized cost per insertion: O(n)/n = O(1)

Space Complexity

Space overhead = capacity - size

With doubling strategy:
- Best case: size = capacity (0% waste)
- Worst case: size = capacity/2 + 1 (~50% waste)
- Average waste: ~25%

Memory usage vs array length:
┌────────────────────────────────────────────────────┐
│     ████████████████████████████                   │ Used
│                                 ░░░░░░░░░░░░░░░░░░░│ Reserved
│  0        capacity/2        capacity               │
└────────────────────────────────────────────────────┘

---

Memory Management Strategies

Strategy 1: Aggressive Shrinking

/* Shrink immediately when below threshold */
void aggressive_shrink(DynArray *arr) {
    if (arr->size > 0 && arr->size <= arr->capacity / 4) {
        size_t new_cap = arr->capacity / 2;
        if (new_cap < 4) new_cap = 4;

        void *new_data = realloc(arr->data, new_cap * sizeof(int));
        if (new_data) {
            arr->data = new_data;
            arr->capacity = new_cap;
        }
    }
}

Strategy 2: Lazy Shrinking

/* Only shrink when explicitly requested */
void lazy_shrink(DynArray *arr) {
    /* Only shrink_to_fit() triggers shrink */
    /* Normal operations never reduce capacity */
}

Strategy 3: Threshold-Based

/* Shrink when significantly oversized */
#define SHRINK_THRESHOLD 0.25  /* Shrink if < 25% full */
#define MIN_CAPACITY 16

void threshold_shrink(DynArray *arr) {
    if (arr->capacity <= MIN_CAPACITY) return;

    double utilization = (double)arr->size / arr->capacity;
    if (utilization < SHRINK_THRESHOLD) {
        size_t target = arr->size * 2;  /* Target 50% utilization */
        if (target < MIN_CAPACITY) target = MIN_CAPACITY;

        void *new_data = realloc(arr->data, target * sizeof(int));
        if (new_data) {
            arr->data = new_data;
            arr->capacity = target;
        }
    }
}

---

Common Patterns and Use Cases

Pattern 1: Stack (LIFO)

typedef IntVector Stack;

Stack *stack_new(void) { return intvec_new(); }
void stack_free(Stack *s) { intvec_free(s); }
int stack_push(Stack *s, int v) { return intvec_push(s, v); }
int stack_pop(Stack *s) { return intvec_pop(s); }
int stack_peek(Stack *s) { return s->size > 0 ? s->data[s->size-1] : 0; }
int stack_empty(Stack *s) { return intvec_empty(s); }

Pattern 2: Queue with Circular Buffer

typedef struct {
    int *data;
    size_t capacity;
    size_t head;  /* Dequeue position */
    size_t tail;  /* Enqueue position */
    size_t size;
} CircularQueue;

CircularQueue *cq_create(size_t capacity) {
    CircularQueue *q = malloc(sizeof(CircularQueue));
    if (!q) return NULL;

    q->data = malloc(capacity * sizeof(int));
    if (!q->data) {
        free(q);
        return NULL;
    }

    q->capacity = capacity;
    q->head = 0;
    q->tail = 0;
    q->size = 0;
    return q;
}

int cq_enqueue(CircularQueue *q, int value) {
    if (q->size >= q->capacity) {
        /* Need to grow */
        size_t new_cap = q->capacity * 2;
        int *new_data = malloc(new_cap * sizeof(int));
        if (!new_data) return -1;

        /* Copy in order */
        for (size_t i = 0; i < q->size; i++) {
            new_data[i] = q->data[(q->head + i) % q->capacity];
        }

        free(q->data);
        q->data = new_data;
        q->capacity = new_cap;
        q->head = 0;
        q->tail = q->size;
    }

    q->data[q->tail] = value;
    q->tail = (q->tail + 1) % q->capacity;
    q->size++;
    return 0;
}

int cq_dequeue(CircularQueue *q) {
    if (q->size == 0) return 0;

    int value = q->data[q->head];
    q->head = (q->head + 1) % q->capacity;
    q->size--;
    return value;
}

void cq_free(CircularQueue *q) {
    if (q) {
        free(q->data);
        free(q);
    }
}

Pattern 3: String Builder

typedef struct {
    char *data;
    size_t length;
    size_t capacity;
} StringBuilder;

StringBuilder *sb_new(void) {
    StringBuilder *sb = malloc(sizeof(StringBuilder));
    if (!sb) return NULL;

    sb->data = malloc(64);
    if (!sb->data) {
        free(sb);
        return NULL;
    }

    sb->data[0] = '\0';
    sb->length = 0;
    sb->capacity = 64;
    return sb;
}

int sb_append(StringBuilder *sb, const char *str) {
    size_t len = strlen(str);
    size_t needed = sb->length + len + 1;

    if (needed > sb->capacity) {
        size_t new_cap = sb->capacity;
        while (new_cap < needed) new_cap *= 2;

        char *new_data = realloc(sb->data, new_cap);
        if (!new_data) return -1;

        sb->data = new_data;
        sb->capacity = new_cap;
    }

    strcpy(sb->data + sb->length, str);
    sb->length += len;
    return 0;
}

char *sb_to_string(StringBuilder *sb) {
    char *result = malloc(sb->length + 1);
    if (result) {
        strcpy(result, sb->data);
    }
    return result;
}

void sb_free(StringBuilder *sb) {
    if (sb) {
        free(sb->data);
        free(sb);
    }
}

---

Best Practices

1. Choose Appropriate Initial Capacity

/* If you know approximate size, use it */
DynArray *arr = dynarray_create_with_capacity(sizeof(int), 1000);

/* Avoids many reallocations during filling */
for (int i = 0; i < 1000; i++) {
    dynarray_push(arr, &i);  /* No reallocation needed */
}

2. Use Safe Reallocation Patterns

/* ALWAYS use temporary for realloc */
void *temp = realloc(arr->data, new_size);
if (temp == NULL) {
    /* Handle error - arr->data still valid! */
    return -1;
}
arr->data = temp;

3. Clear vs Destroy

/* Clear: Keep capacity, reset size */
void dynarray_clear(DynArray *arr) {
    arr->size = 0;
    /* Capacity unchanged - reuse memory */
}

/* Destroy: Free everything */
void dynarray_destroy(DynArray *arr) {
    free(arr->data);
    free(arr);
}

4. Consider Memory Locality

/* Prefer contiguous allocation for cache efficiency */
Matrix *m = matrix_create(1000, 1000);  /* Single allocation */

/* Avoid many small allocations */
/* BAD: row[i] = malloc(cols * sizeof(int)); in loop */

5. Document Ownership

/**
 * @brief Appends a copy of element to the array.
 * @param arr Target array
 * @param element Pointer to element to copy
 * @return 0 on success, -1 on failure
 * @note Array takes ownership of the copy, not the original.
 */
int dynarray_push(DynArray *arr, const void *element);

---

Summary

Key Concepts

1. •Dynamic arrays provide resizable, heap-allocated storage
2. •Size vs Capacity: actual elements vs allocated space
3. •Growth strategies balance memory vs reallocation cost
4. •2D arrays can use pointers-to-pointers or contiguous blocks

When to Use Dynamic Arrays

• •Unknown size at compile time
• •Size varies during execution
• •Need to persist beyond function scope
• •Implementing stacks, queues, or similar structures

Memory Management Checklist

• • Initialize pointers to NULL
• • Check all allocation results
• • Use temp variable for realloc
• • Free in reverse order of allocation
• • Set pointer to NULL after free

Quick Reference

/* Create */
DynArray *arr = dynarray_create(sizeof(int));

/* Add elements */
dynarray_push(arr, &value);
dynarray_insert(arr, index, &value);

/* Access elements */
int *ptr = dynarray_get(arr, index);

/* Remove elements */
dynarray_pop(arr, &out);
dynarray_remove(arr, index, &out);

/* Query */
size_t n = dynarray_size(arr);
int empty = dynarray_is_empty(arr);

/* Memory management */
dynarray_reserve(arr, min_capacity);
dynarray_shrink_to_fit(arr);
dynarray_clear(arr);
dynarray_destroy(arr);

---

Next Steps

After mastering dynamic arrays:

• •Implement linked lists for frequent insertions/deletions
• •Study hash tables for O(1) access by key
• •Learn about memory pools for high-performance allocation
• •Explore std::vector (C++) for comparison

---

This tutorial is part of the C Programming Learning Series.