Dynamic Array Data Structure

A linear list represents a finite sequence of elements sharing identical characteristics. Logically, it forms a continuous line, but its physical memory layout can vary. The dynamic array, a specific linear list implementation, reserves contiguous memory blocks to store elements, growing its allocated space when necessary to accommodate insertions.

Data Structure Definition

We define a customizable type alias for the stored values, allowing easy modification of the element type without altering the core logic. The structure maintains a pointer to the allocated buffer, the current number of valid entries, and the total allocated slots.

typedef int Item;

typedef struct {
    Item* buffer;
    int length;
    int max_size;
} Vector;

Initialization and Cleanup

Before usage, the structure must be initialized to a clean state. Passing the structure's address is crucial; otherwise, modifications affect only a local copy. Cleanup requires releasing the dynamically allocated heap memory and resetting the tracking fields to prevent leaks.

void VecInit(Vector* v) {
    v->buffer = NULL;
    v->length = 0;
    v->max_size = 0;
}

void VecDispose(Vector* v) {
    if (v->buffer != NULL) {
        free(v->buffer);
        v->buffer = NULL;
    }
    v->length = 0;
    v->max_size = 0;
}

Capacity Management

Before adding elements, we must verify that sufficient space exists. If the current length equals the maximum allocated size, expansion is required. We double the capacity, or set an initial baseline size if currently empty. Utilizing realloc handles memory reallocation, copying, and old block freeing seamlessly.

void ExpandIfFull(Vector* v) {
    if (v->length == v->max_size) {
        int new_cap = (v->max_size == 0) ? 4 : v->max_size * 2;
        Item* new_buf = realloc(v->buffer, new_cap * sizeof(Item));
        if (!new_buf) {
            perror("Allocation failure");
            exit(EXIT_FAILURE);
        }
        v->buffer = new_buf;
        v->max_size = new_cap;
    }
}

Insert Operations

Appending an element involves checking capacity and placing the new value at the end.

void VecAppend(Vector* v, Item val) {
    ExpandIfFull(v);
    v->buffer[v->length] = val;
    v->length++;
}

Prepending requires shifting all existing elements one position to the right to free the initial slot. A descending loop prevents overwriting adjacent data prematurely.

void VecPrepend(Vector* v, Item val) {
    ExpandIfFull(v);
    for (int i = v->length; i > 0; i--) {
        v->buffer[i] = v->buffer[i - 1];
    }
    v->buffer[0] = val;
    v->length++;
}

For arbitrary insertion at a specific zero-based index, we shift elements from that index onward towards the end, then place the new value.

void VecInsertAt(Vector* v, int idx, Item val) {
    assert(v != NULL);
    assert(idx >= 0 && idx <= v->length);
    ExpandIfFull(v);
    for (int i = v->length; i > idx; i--) {
        v->buffer[i] = v->buffer[i - 1];
    }
    v->buffer[idx] = val;
    v->length++;
}

Deletion Operations

Removing the last element simply decrements the length counter, provided the container is not empty.

void VecRemoveLast(Vector* v) {
    assert(v != NULL);
    assert(v->length > 0);
    v->length--;
}

Removing the first element requires shifting all subsequent items one position to the left using an ascending loop.

void VecRemoveFirst(Vector* v) {
    assert(v != NULL);
    assert(v->length > 0);
    for (int i = 0; i < v->length - 1; i++) {
        v->buffer[i] = v->buffer[i + 1];
    }
    v->length--;
}

Deleting at an arbitrary zero-based index involves a similar left-shift of elements following the target position.

void VecDeleteAt(Vector* v, int idx) {
    assert(v != NULL);
    assert(idx >= 0 && idx < v->length);
    for (int i = idx; i < v->length - 1; i++) {
        v->buffer[i] = v->buffer[i + 1];
    }
    v->length--;
}