# 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.

```c
#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:

```c
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:

```c
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:

```c
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:

```c
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:

```c
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:

```c
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:

```c
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:

```c
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:

```c
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:

```c
#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.