Structure Definition

Using a type alias simplifies future modifications to the stored data type. Changing the alias definition updates the type across the entire codebase without altering multiple declarations.

typedef int Item;
typedef struct {
    Item* data;
    int count;
    int limit;
} DynamicVector;

Capacity Validation Helper

To avoid duplicating memory allocation logic, a helper function checks if the array is full and doubles its capacity using realloc.

void ensure_capacity(DynamicVector* vec) {
    if (vec->count == vec->limit) {
        int new_limit = vec->limit * 2;
        Item* new_data = (Item*)realloc(vec->data, new_limit * sizeof(Item));
        if (!new_data) {
            perror("Allocation failed");
            exit(EXIT_FAILURE);
        }
        vec->data = new_data;
        vec->limit = new_limit;
    }
}

Initialization

Set the initial state. The buffer starts as NULL, the element count is zero, and the initial capacity is set to a small baseline like 4 to prepare for the first expansion.

void vector_init(DynamicVector* vec) {
    vec->data = NULL;
    vec->count = 0;
    vec->limit = 4;
}

Destruction

Release the dynamically allocated buffer and nullify the pointer to prevent dangling references. Reset tracking integers to zero.

void vector_destroy(DynamicVector* vec) {
    if (vec->data != NULL) {
        free(vec->data);
    }
    vec->data = NULL;
    vec->count = 0;
    vec->limit = 0;
}

Append Element

Inserting at the end requires ensuring sufficient capacity. If space is available, the new element is placed at the current count index, and the count increments.

void push_back(DynamicVector* vec, Item val) {
    ensure_capacity(vec);
    vec->data[vec->count] = val;
    vec->count++;
}

Prepend Element

Inserting at the beginning requires shifting all existing elements one position to the right to make room at index zero. Capacity validation is required before shifting.

void push_front(DynamicVector* vec, Item val) {
    ensure_capacity(vec);
    for (int i = vec->count; i > 0; --i) {
        vec->data[i] = vec->data[i - 1];
    }
    vec->data[0] = val;
    vec->count++;
}

Remove First Element

To delete the leading element, shift all subsequent elements one position to the left, overwriting the first element. Decrement the count afterwards.

bool is_empty(DynamicVector* vec) {
    return vec->count == 0;
}

void pop_front(DynamicVector* vec) {
    assert(!is_empty(vec));
    for (int i = 0; i < vec->count - 1; ++i) {
        vec->data[i] = vec->data[i + 1];
    }
    vec->count--;
}

Remove Last Element

Removing from the end simply requires decrementing the count. The next insertion will naturally overwrite the old data.

void pop_back(DynamicVector* vec) {
    assert(!is_empty(vec));
    vec->count--;
}

Insert at Position

This generalizes insertion at any valid index. Elements from the target index to the end are shifted right, and the new value is placed at the target index. This encompasses both prepend and append operations.

void insert_at(DynamicVector* vec, int idx, Item val) {
    assert(idx >= 0 && idx <= vec->count);
    ensure_capacity(vec);
    for (int i = vec->count; i > idx; --i) {
        vec->data[i] = vec->data[i - 1];
    }
    vec->data[idx] = val;
    vec->count++;
}

Erase at Position

This generalizes deletion at any valid index. Elements after the target index are shifted left, overwriting the target. This encompasses both front and back deletions.

void erase_at(DynamicVector* vec, int idx) {
    assert(!is_empty(vec));
    assert(idx >= 0 && idx < vec->count);
    for (int i = idx; i < vec->count - 1; ++i) {
        vec->data[i] = vec->data[i + 1];
    }
    vec->count--;
}

Find Element

Iterate through the array to check for the target value. Return true if found, otherwise return false.

bool contains(DynamicVector* vec, Item val) {
    for (int i = 0; i < vec->count; ++i) {
        if (vec->data[i] == val) return true;
    }
    return false;
}