A Complete Guide - C Programming data structures Dynamic Arrays ArrayList, Vector

Example 1: Simple Dynamic Array (ArrayList)

Step 1: Include Necessary Headers

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

Step 2: Define a Structure for the ArrayList

typedef struct {
    int *elements;
    int capacity;
    int size;
} ArrayList;

Here, we define an ArrayList structure that has a pointer to an array (elements), the current capacity of the array (capacity), and the current number of elements in the array (size).

Step 3: Initialization Function

Create a function to initialize the ArrayList.

void initArrayList(ArrayList *arrList, int initialCapacity) {
    arrList->elements = (int *)malloc(initialCapacity * sizeof(int));
    arrList->capacity = initialCapacity;
    arrList->size = 0;
}

The initArrayList function allocates memory for the elements array and sets the initial capacity and size.

Step 4: Resize Function

Implement a function to resize the ArrayList when necessary.

void resizeArrayList(ArrayList *arrList) {
    arrList->capacity *= 2; // Double the capacity
    arrList->elements = (int *)realloc(arrList->elements, arrList->capacity * sizeof(int));
    if (arrList->elements == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(1);
    }
}

This resizeArrayList function doubles the capacity when needed and reallocates the memory accordingly.

Step 5: Add Element Function

Add a function to add elements to the ArrayList.

void addElement(ArrayList *arrList, int value) {
    if (arrList->size == arrList->capacity) {
        resizeArrayList(arrList);
    }
    arrList->elements[arrList->size++] = value;
}

The addElement function checks if the current size has reached the capacity. If so, it resizes the list before adding the new element.

Step 6: Print Elements Function

Create a function to print all elements in the ArrayList.

void printElements(ArrayList *arrList) {
    for (int i = 0; i < arrList->size; i++) {
        printf("%d ", arrList->elements[i]);
    }
    printf("\n");
}

The printElements function iterates through the elements array and prints each one.

Step 7: Main Function to Demonstrate Usage

int main() {
    ArrayList arrList;
    initArrayList(&arrList, 10); // Initial capacity is 10

    // Adding elements to the ArrayList
    for (int i = 0; i < 15; i++) { // Add numbers 0 to 14
        addElement(&arrList, i);
        printf("Added element %d: ", i);
        printElements(&arrList);
    }

    // Freeing allocated memory
    free(arrList.elements);

    return 0;
}

Explanation:

• Initialization: The initArrayList function sets up the ArrayList with an initial capacity. In this example, the initial capacity is 10.

• Adding Elements: As elements are added with addElement, the function checks if the array needs resizing. If the size reaches the capacity, the resizeArrayList function doubles the capacity and reallocates memory.

• Printing Elements: The printElements function displays all the elements currently stored in the ArrayList.

• Main Function: Demonstrates how to use the ArrayList by adding elements up to 14, which triggers a resize after the capacity is filled.

Example 2: Implementing a Vector

A Vector in C can be similar to the ArrayList, but often has a bit more functionality such as element removal, searching, etc.

Step 1: Define a Structure for the Vector

typedef struct {
    int *elements;
    int capacity;
    int size;
} Vector;

Step 2: Initialization Function

Create a function to initialize the Vector.

void initVector(Vector *vec, int initialCapacity) {
    vec->elements = (int *)malloc(initialCapacity * sizeof(int));
    if (vec->elements == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(1);
    }
    vec->capacity = initialCapacity;
    vec->size = 0;
}

Step 3: Resize Function

Implement a function to resize the Vector when necessary.

void resizeVector(Vector *vec) {
    vec->capacity *= 2;
    vec->elements = (int *)realloc(vec->elements, vec->capacity * sizeof(int));
    if (vec->elements == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(1);
    }
}

Step 4: Add Element Function

void addElementVector(Vector *vec, int value) {
    if (vec->size == vec->capacity) {
        resizeVector(vec);
    }
    vec->elements[vec->size++] = value;
}

Step 5: Remove Element Function

Add a function to remove the last element from the Vector.

void removeLastElementVector(Vector *vec) {
    if (vec->size == 0) {
        fprintf(stderr, "Cannot remove element from empty vector\n");
        return;
    }
    vec->size--; // Simply reduce the size
}

Step 6: Get Element Function

Add a function to retrieve an element at a specific index.

int getElementVector(Vector *vec, int index) {
    if (index < 0 || index >= vec->size) {
        fprintf(stderr, "Index out of bounds\n");
        exit(1);
    }
    return vec->elements[index];
}

Step 7: Print Elements Function

Create a function to print all elements in the Vector.

void printElementsVector(Vector *vec) {
    for (int i = 0; i < vec->size; i++) {
        printf("%d ", vec->elements[i]);
    }
    printf("\n");
}

Step 8: Main Function to Demonstrate Usage

int main() {
    Vector vec;
    initVector(&vec, 5); // Initial capacity is 5

    // Adding elements to the Vector
    for (int i = 0; i < 8; i++) { // Add numbers 0 to 7
        addElementVector(&vec, i);
        printf("Added element %d: ", i);
        printElementsVector(&vec);
    }

    // Removing elements from the Vector
    for (int i = 0; i < 3; i++) { // Remove numbers 7, 6, 5
        printf("Removing last element: ");
        printElementsVector(&vec);
        removeLastElementVector(&vec);
    }

    // Freeing allocated memory
    free(vec.elements);

    return 0;
}

Explanation:

• Initialization: The initVector function sets up the Vector with an initial capacity. Here, the initial capacity is 5.

• Adding Elements: As elements are added with addElementVector, the function checks if the array needs resizing.

• Removing Elements: The removeLastElementVector function simply reduces the size, which effectively removes the last element since it won't be accessed again.

• Get Element: The getElementVector function retrieves the element at the specified index, ensuring that the index is within bounds.

• Print Elements: The printElementsVector function displays all the elements currently stored in the Vector.

• Main Function: Demonstrates using the Vector to add elements from 0 to 7, triggering one resize because of the capacity, and then removing the last three elements.