A dynamic array is an array that can automatically resize itself when its capacity is exceeded.

This is achieved by allocating a new, larger block of memory, copying the existing elements from the old array, and freeing the old memory.

This is known in Python typically as a ‘re-sizeable array’.

In Java and C++ respectively, you will know this ArrayList and vector .

The key advantage of dynamic arrays is the ability to work in variable-size allocations without worrying about memory allocation.

This approach will be preferred in situations where an application’s most logical memory size is unknown or is too difficult to calculate before the array is given its allocation.

Dynamic Array in C

To explore dynamic arrays we will use a language ‘close’ to the computer, the obvious choice is C.

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

typedef struct {
    int* data;      // data points to our dynamic array
    int capacity;   // capacity of array
    int size;       // size of array
} DynamicArray;

// Functions
DynamicArray* createDynamicArray(int capacity);
void insertElement(DynamicArray* arr, int element);
int removeElement(DynamicArray* arr);
void resizeArray(DynamicArray* arr, int newCapacity);
void freeDynamicArray(DynamicArray* arr);

First, we create a data structure DynamicArray and then define the functions we will use to manage it.

Creating a Dynamic Array

For those familiar with C, the use of malloc is predictable and expected in a situation like this.

The C function malloc allows us to allocate memory for our dynamically set DynamicArray.

By taking the sizeof our DynamicArray , we can fetch the number of elements in our array.

We also dynamically allocate memory for our data as well.

Finally, we initialize the capacity member with the provided capacity set the size member to 0, and returns a pointer to the dynamically created DynamicArray structure.

DynamicArray* createDynamicArray(int capacity) {
    DynamicArray* arr = (DynamicArray*)malloc(sizeof(DynamicArray));
    arr->data = (int*)malloc(capacity * sizeof(int));
    arr->capacity = capacity;
    arr->size = 0;
    return arr;
}

Resizing the Array

The resizeArray function is responsible for allocating a new memory block with the desired capacity, copying the existing elements, and freeing the old memory.

The logic behind our loop is fairly simple. Iterate through the current array and copy its value to the corresponding position in the new array newdata .

void resizeArray(DynamicArray* arr, int newCapacity) {
    int* newData = (int*)malloc(newCapacity * sizeof(int));
    for (int i = 0; i < arr->size; i++) {
        newData[i] = arr->data[i];
    }
    free(arr->data);
    arr->data = newData;
    arr->capacity = newCapacity;
}

Inserting an Element

The insertElement function adds a new element to the end of the dynamic array.

If the array is full, it calls the resizeArray function to double the capacity.

Our loop checks if our array size equals our array capacity. We use resizeArray within our loop to double the array if it does not equal its capacity.

void insertElement(DynamicArray* arr, int element) {
    if (arr->size == arr->capacity) {
        resizeArray(arr, arr->capacity * 2);
    }
    arr->data[arr->size] = element;
    arr->size++;
}

Removing an Element

The removeElement function removes the last element from the dynamic array and returns its value.

If the array's size drops below a certain threshold (e.g., 25% of the capacity), it calls resizeArray to halve the capacity.

int removeElement(DynamicArray* arr) {
    if (arr->size == 0) {
        printf("Error: Array is empty\n");
        return -1;
    }
    int element = arr->data[arr->size - 1];
    arr->size--;
    if (arr->size < arr->capacity / 4) {
        resizeArray(arr, arr->capacity / 2);
    }
    return element;
}

Freeing the Dynamic Array

When you’re done using the dynamic array in C, it’s essential to free the allocated memory to avoid memory leaks.

The freeDynamicArray function takes care of this.

void freeDynamicArray(DynamicArray* arr) {
    free(arr->data);
    free(arr);
}

Full Application for Array Manipulation

#include <stdio.h>

int main() {
    DynamicArray* arr = createDynamicArray(2);

    insertElement(arr, 10);
    insertElement(arr, 20);
    insertElement(arr, 30); // This will trigger a resize

    printf("Array elements: ");
    for (int i = 0; i < arr->size; i++) {
        printf("%d ", arr->data[i]);
    }
    printf("\n");

    int removedElement = removeElement(arr);
    printf("Removed element: %d\n", removedElement);

    freeDynamicArray(arr);

    return 0;
}

This example creates a dynamic array with an initial capacity of 2, inserts three elements (triggering a resize), prints the array elements, removes the last element, and frees the dynamic array memory.

When to Use a Dynamic Array?

Prospective C developers should consider the following when considering the usage of a dynamic array in an application.

1. Increase Memory Efficiency: By dynamically resizing the array when needed, memory usage is optimized.

2. Increase Performance: The dynamic resizing strategy used in the code ensures that the array can grow as needed without having to allocate a new, larger array every time it reaches capacity.

3. Possible Flexibility: Dynamic arrays allow for flexible data storage, enabling applications to handle data without wasting memory or causing runtime errors.

4. Possible Scalability: This code enables applications to handle larger datasets without having to rewrite or redesign data structures.

5. Improved Resource Management: By automatically resizing the array as needed, the code simplifies resource management for developers.

Real World Applications

• File I/O Operations: A dynamic array can be used to store data as it is read, allowing the array to grow or shrink as needed.

• Networking: A dynamic array can be used to store incoming or outgoing data, accommodating different packet sizes without wasting memory or imposing unnecessary limits.

• Parsing and Tokenization: A dynamic array can be used to store tokens or substrings, growing or shrinking as needed during the parsing process.

• Garbage Collection: In garbage collectors, dynamic arrays can be used to keep track of allocated memory blocks or objects.

• Compression and Decompression: A dynamic array can be used to store compressed or decompressed data, adjusting its size as needed during the compression or decompression process.

Strategy Pattern Design In Practice

• Single Responsibility Principle (SRP): Each function in the implementation has a single, well-defined responsibility.

• Open/Closed Principle (OCP): The dynamic array implementation is open for extension but closed for modification.

• Abstraction: The internals of the dynamic array (data, capacity, and size) are hidden from the outside world.

• Don’t Repeat Yourself (DRY): The code follows the DRY principle by centralizing common operations, such as memory allocation and resizing, into reusable functions (resizeArray).

• Modularity: The dynamic array implementation is designed as a self-contained module, with a clear interface (function prototypes) and internal implementation details.

Conclusion

Dynamic arrays provide a flexible way to manage variable-sized collections in C.

With this implementation, you can confidently work with arrays without worrying about fixed sizes or memory constraints, making your code more robust and scalable.

-Nick