Bigger Example 3: Dynamic Array

Question: Implement a dynamic array data structure in C that supports the following operations:

1. Initialization with an initial capacity.

2. Accessing an element at a given index.

3. Setting the value at a given index.

4. Inserting a new element at a specific index (with automatic capacity adjustment if necessary).

5. Removing an element at a specific index (with automatic capacity adjustment if necessary).

Your implementation should dynamically resize the array to accommodate additional elements and efficiently manage memory.

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

#define INITIAL_CAPACITY 10
#define GROWTH_FACTOR 2

typedef struct {
    int *array;
    size_t size;
    size_t capacity;
} DynamicArray;

// Function prototypes
DynamicArray* initDynamicArray(size_t initialCapacity);
int get(DynamicArray *arr, size_t index);
void set(DynamicArray *arr, size_t index, int value);
void insert(DynamicArray *arr, size_t index, int value);
void removeAt(DynamicArray *arr, size_t index);
void resizeIfNeeded(DynamicArray *arr);

// Function to initialize a dynamic array with a given initial capacity
DynamicArray* initDynamicArray(size_t initialCapacity) {
    DynamicArray *arr = (DynamicArray *)malloc(sizeof(DynamicArray));
    arr->array = (int *)malloc(initialCapacity * sizeof(int));
    arr->size = 0;
    arr->capacity = initialCapacity;
    return arr;
}

// Function to get the value at a specific index
int get(DynamicArray *arr, size_t index) {
    if (index < arr->size) {
        return arr->array[index];
    } else {
        // Handle index out of bounds
        fprintf(stderr, "Error: Index out of bounds\n");
        exit(EXIT_FAILURE);
    }
}

// Function to set the value at a specific index
void set(DynamicArray *arr, size_t index, int value) {
    if (index < arr->size) {
        arr->array[index] = value;
    } else {
        // Handle index out of bounds
        fprintf(stderr, "Error: Index out of bounds\n");
        exit(EXIT_FAILURE);
    }
}

// Function to insert a value at a specific index
void insert(DynamicArray *arr, size_t index, int value) {
    if (index > arr->size) {
        // Handle index out of bounds
        fprintf(stderr, "Error: Index out of bounds\n");
        exit(EXIT_FAILURE);
    }

    resizeIfNeeded(arr);

    // Shift elements to make space for the new element
    for (size_t i = arr->size; i > index; --i) {
        arr->array[i] = arr->array[i - 1];
    }

    // Insert the new element
    arr->array[index] = value;
    arr->size++;
}

// Function to remove an element at a specific index
void removeAt(DynamicArray *arr, size_t index) {
    if (index >= arr->size) {
        // Handle index out of bounds
        fprintf(stderr, "Error: Index out of bounds\n");
        exit(EXIT_FAILURE);
    }

    // Shift elements to fill the gap left by the removed element
    for (size_t i = index; i < arr->size - 1; ++i) {
        arr->array[i] = arr->array[i + 1];
    }

    arr->size--;

    // Resize the array if the size becomes significantly smaller than the capacity
    resizeIfNeeded(arr);
}

// Function to resize the array if needed
void resizeIfNeeded(DynamicArray *arr) {
    if (arr->size >= arr->capacity) {
        arr->capacity *= GROWTH_FACTOR;
        arr->array = (int *)realloc(arr->array, arr->capacity * sizeof(int));
        if (arr->array == NULL) {
            // Handle memory allocation failure
            fprintf(stderr, "Error: Memory allocation failed\n");
            exit(EXIT_FAILURE);
        }
    } else if (arr->size <= arr->capacity / (2 * GROWTH_FACTOR)) {
        // Reduce the capacity if the size becomes significantly smaller than the capacity
        arr->capacity /= GROWTH_FACTOR;
        arr->array = (int *)realloc(arr->array, arr->capacity * sizeof(int));
        if (arr->array == NULL) {
            // Handle memory allocation failure
            fprintf(stderr, "Error: Memory allocation failed\n");
            exit(EXIT_FAILURE);
        }
    }
}

// Main function for testing
int main() {
    // Example usage
    DynamicArray *arr = initDynamicArray(INITIAL_CAPACITY);

    for (int i = 0; i < 15; ++i) {
        insert(arr, i, i * 2);
    }

    for (int i = 0; i < arr->size; ++i) {
        printf("%d ", get(arr, i));
    }
    printf("\n");

    set(arr, 2, 99);

    for (int i = 0; i < arr->size; ++i) {
        printf("%d ", get(arr, i));
    }
    printf("\n");

    removeAt(arr, 3);

    for (int i = 0; i < arr->size; ++i) {
        printf("%d ", get(arr, i));
    }
    printf("\n");

    // Free allocated memory
    free(arr->array);
    free(arr);

    return 0;
}

Let's examine the code in detail:

1. Structure Definition:

typedef struct {
    int *array;
    size_t size;
    size_t capacity;
} DynamicArray;

• DynamicArray is a structure representing the dynamic array.

• array is a pointer to an array of integers, where the actual data is stored.

• size is the current number of elements in the array.

• capacity is the maximum number of elements that the current array can hold.

2. Function Prototypes:

DynamicArray* initDynamicArray(size_t initialCapacity);
int get(DynamicArray *arr, size_t index);
void set(DynamicArray *arr, size_t index, int value);
void insert(DynamicArray *arr, size_t index, int value);
void removeAt(DynamicArray *arr, size_t index);
void resizeIfNeeded(DynamicArray *arr);

• initDynamicArray: Allocates memory for a DynamicArray structure and initializes its fields.

• get: Retrieves the value at a specified index in the array.

• set: Sets the value at a specified index in the array.

• insert: Inserts a new element at a specified index, shifting existing elements.

• removeAt: Removes an element at a specified index, shifting elements to fill the gap.

• resizeIfNeeded: Checks if resizing is necessary based on the current size and capacity of the array.

3. initDynamicArray Function:

DynamicArray* initDynamicArray(size_t initialCapacity) {
    DynamicArray *arr = (DynamicArray *)malloc(sizeof(DynamicArray));
    arr->array = (int *)malloc(initialCapacity * sizeof(int));
    arr->size = 0;
    arr->capacity = initialCapacity;
    return arr;
}

• Allocates memory for a DynamicArray structure and its internal array.

• Sets the initial size to 0 and the capacity to the specified initial capacity.

• Returns a pointer to the created DynamicArray.

4. get and set Functions:

int get(DynamicArray *arr, size_t index) {
    // ...
}

void set(DynamicArray *arr, size_t index, int value) {
    // ...
}

• get: Returns the value at the specified index if it's within bounds, otherwise, prints an error message and exits.

• set: Sets the value at the specified index if it's within bounds, otherwise, prints an error message and exits.

5. insert Function:

void insert(DynamicArray *arr, size_t index, int value) {
    // ...
}

• Checks if the index is out of bounds and handles the error.

• Calls resizeIfNeeded to ensure there's enough space for the new element.

• Shifts elements to the right to make space for the new element.

• Inserts the new element at the specified index and increments the size.

6. removeAt Function:

void removeAt(DynamicArray *arr, size_t index) {
    // ...
}

• Checks if the index is out of bounds and handles the error.

• Shifts elements to the left to fill the gap left by the removed element.

• Decrements the size.

• Calls resizeIfNeeded to adjust the capacity if necessary.

7. resizeIfNeeded Function:

void resizeIfNeeded(DynamicArray *arr) {
    // ...
}

• Checks if the size exceeds the capacity. If true, it doubles the capacity.

• Checks if the size is significantly smaller than the capacity. If true, it halves the capacity.

• Uses realloc to resize the internal array.

• Handles errors if memory allocation fails.

8. main Function:

int main() {
    // ...
}

• Example usage of the dynamic array functions to insert, set, and remove elements.

• Prints the array at different stages.

• Frees the allocated memory.

9. Memory Deallocation:

free(arr->array);
free(arr);

• Frees the memory allocated for the internal array and the DynamicArray structure.

In the provided C code, the growth factor is defined as 2 in the line:

#define GROWTH_FACTOR 2

The dynamic array is resized using the growth factor. The array's capacity is doubled by the growth factor whenever its current size exceeds its capacity, indicating that inserting a new element would surpass the current size. Alternatively, the array can be enlarged by dividing its capacity by the growth factor. This is done when the size becomes significantly smaller than the capacity, which can occur during removal operations. If additional elements need to be added to the array, its size will be doubled due to the growth factor of 2 in this specific implementation. Memory consumption and the frequency of resizing operations are two factors to consider when choosing an appropriate growth factor. A growth factor of 2 is often used because it strikes a reasonable balance between these two factors.