Dynamically Growing Array In C

Dynamically Growing Array In C

A Dynamically Growing Array is a type of dynamic array that can expand in size to store data as required. In the C language, static arrays have fixed sizes known at compile time, which can lead to space issues.

Programming languages like C++, Python, and Java have built-in data structures that manage size automatically. The goal is to create a dynamic array in C that can adjust its size dynamically to meet the program’s requirements, thus avoiding issues with wasted memory or running out of space.

Basic Principle

The fundamental principle of the Dynamically Growing Array is based on the dynamic memory allocation concept in C. This concept enables users to allocate memory during program execution and adjust the allocated size as needed.

Working

1. Start with a Small Initial Size: The newly created dynamic array begins with a small initial size to save memory.
2. Provide Standard Array Operations: Functions are available to perform typical array operations, like adding, accessing, or removing elements, just as you would with a regular array.
3. Double the Capacity When Needed: When the array runs out of space, its capacity is doubled by using the realloc() function to reallocate memory. Doubling the size is preferred over increasing it one by one because multiple realloc() calls can be costly and may impact the efficiency of insertion operations.
4. Amortized Constant Time Complexity: Doubling the array’s size has amortized constant time complexity for insertion operations, making it efficient in practice.
5. **Clear Memory with free()**: After the array is no longer needed, the memory is released using thefree()` function to prevent memory leaks.

This approach ensures that the Dynamically Growing Array is both memory-efficient and time-efficient for various operations.

C Program for Dynamically Growing Array

// C program to demonstrate the  
// dynamically growing array 
#include <stdio.h> 
#include <stdlib.h> 
  
#define INITIAL_SIZE 8 
  
// base structure 
typedef struct { 
    size_t size; 
    size_t capacity; 
    int* array; 
}dynamic_array; 
  
// function prototypes 
//  array container functions 
void arrayInit(dynamic_array** arr_ptr); 
void freeArray(dynamic_array* container); 
  
// Basic Operation functions 
void insertItem(dynamic_array* container, int item); 
void updateItem(dynamic_array* container, int i, int item); 
int getItem(dynamic_array* container, int i); 
void deleteItem(dynamic_array* container, int item); 
void printArray(dynamic_array* container); 
  
// driver code 
int main() 
{ 
    dynamic_array* arr; 
    arrayInit(&arr); 
      
    for (int i = 0; i < 6; i++) { 
        insertItem(arr, i + 11); 
    } 
    printArray(arr); 
    printf("%d\n", getItem(arr, 3)); 
    deleteItem(arr, 3); 
    printArray(arr); 
  
    for (int i = 0; i < 5; i++) { 
        insertItem(arr, i + 17); 
    } 
  
    printArray(arr); 
  
    freeArray(arr); 
    int var; 
    return 0; 
} 
//------Function Definitions------ 
// Array initialization 
void arrayInit(dynamic_array** arr_ptr) 
{ 
    dynamic_array *container; 
    container = (dynamic_array*)malloc(sizeof(dynamic_array)); 
    if(!container) { 
        printf("Memory Allocation Failed\n"); 
        exit(0); 
    } 
  
    container->size = 0; 
    container->capacity = INITIAL_SIZE; 
    container->array = (int *)malloc(INITIAL_SIZE * sizeof(int)); 
    if (!container->array){ 
        printf("Memory Allocation Failed\n"); 
        exit(0); 
    } 
  
    *arr_ptr = container; 
} 
  
//  Insertion Operation 
void insertItem(dynamic_array* container, int item) 
{ 
if (container->size == container->capacity) { 
        int *temp = container->array; 
        container->capacity <<= 1; 
        container->array = realloc(container->array, container->capacity * sizeof(int)); 
        if(!container->array) { 
            printf("Out of Memory\n"); 
            container->array = temp; 
            return; 
        } 
    } 
    container->array[container->size++] = item; 
} 
  
// Retrieve Item at Particular Index 
int getItem(dynamic_array* container, int index) 
{ 
    if(index >= container->size) { 
        printf("Index Out of Bounds\n"); 
        return -1; 
    } 
    return container->array[index]; 
} 
  
// Update Operation 
void updateItem(dynamic_array* container, int index, int item) 
{ 
    if (index >= container->size) { 
        printf("Index Out of Bounds\n"); 
        return; 
    } 
    container->array[index] = item; 
} 
  
// Delete Item from Particular Index 
void deleteItem(dynamic_array* container, int index) 
{ 
    if(index >= container->size) { 
        printf("Index Out of Bounds\n"); 
        return; 
    } 
  
    for (int i = index; i < container->size; i++) { 
        container->array[i] = container->array[i + 1]; 
    } 
    container->size--; 
} 
  
// Array Traversal 
void printArray(dynamic_array* container) 
{ 
    printf("Array elements: "); 
    for (int i = 0; i < container->size; i++) { 
        printf("%d ", container->array[i]); 
    } 
    printf("\nSize: "); 
    printf("%lu", container->size); 
    printf("\nCapacity: "); 
    printf("%lu\n", container->capacity); 
} 
  
// Freeing the memory allocated to the array 
void freeArray(dynamic_array* container) 
{ 
    free(container->array); 
    free(container); 
}

Output

Array elements: 11 12 13 14 15 16 
Size: 6
Capacity: 8
14
Array elements: 11 12 13 15 16 
Size: 5
Capacity: 8
Array elements: 11 12 13 15 16 17 18 19 20 21 
Size: 10
Capacity: 16

Components of Dynamically Growing Array

1. dynamic_array: The core structure for the dynamic array.
2. arrayInit(): Function to set up and initialize the array.
3. deleteArr(): Function for freeing up memory when done with the array.

1. dynamic_array

1. size: Keeps track of how much memory is being used.
2. capacity: Keeps track of the maximum capacity of the array.
3. array: A pointer to the actual storage location, typically an array of integers (int).

Code

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

2. arrayInit()

This function initializes the dynamic array with a default size of 8. It accepts the address of a double-pointer to the dynamic_array as an argument.

Code:

void arrayInit(dynamic_array** arr_ptr)
{
    dynamic_array *container;
    container = (dynamic_array*)malloc(sizeof(dynamic_array));
    if(!container) {
        printf("Memory Allocation Failed\n");
        exit(0);
    }

    container->size = 0;
    container->capacity = INITIAL_SIZE;
    container->array = (int *)malloc(INITIAL_SIZE * sizeof(int));
    if (!container->array){
        printf("Memory Allocation Failed\n");
        exit(0);
    }

    *arr_ptr = container;
}

3. freeArray()

This function is responsible for releasing the memory allocated to the dynamically growing array. It should be called when you’re finished using the array to ensure proper memory management.

Code:

void freeArray(dynamic_array* container)
{
    free(container->array);
    free(container);
}

Basic Operations

5 basic operations can provide basic operations of an array.

1. insertItem(): Used for adding an element at the end of the array
2. getItem(): This operation is used to recover the element at the given index
3. updateItem(): Used to update an element at that given index of the array
4. printItem(): functions for printing all the elements of the array
5. deleteItem():  Used to delete an element of the array at the given index

1. insertItem()

The insertItem() function allows you to add elements to an array. When there’s available space, it inserts elements without changing the array’s size. However, when the array is full, it uses the realloc() function to double the array’s capacity and then perform the insertion. This strategy optimizes the efficiency of insertions by minimizing the need for frequent resizing.

Code:

void insertItem(dynamic_array* container, int item)
{
    if (container->size == container->capacity) {
        int *temp = container->array;
        container->capacity <<= 1;
        container->array = realloc(container->array, container->capacity * sizeof(int));
        if(!container->array) {
            printf("Out of Memory\n");
            container->array = temp;
            return;
        }
    }
    container->array[container->size++] = item;
}

2. getItem()

This function returns the integer value located at a specified index. It requires two arguments: the container’s address and the index.

int getItem(dynamic_array* container, int index)
{
    if(index > container->size) {
        printf("Index Out of Bounds\n");
        return -1;
    }
    return container->array[index];
}

3. updateItem()

The updateItem() function allows you to update an element at a specific index in a container. It accepts three arguments: the container’s address, the index, and the new updated item.

Code:

void updateItem(dynamic_array* container, int index, int item)
{
    if (index > container->size) {
        printf("Index Out of Bounds\n");
        return;
    }
    container->array[index] = item;
}

4. printItem()

This function will pass over the array and then print all elements. Despite of that, it will also print the current size and capacity of the array.

Code:

void printArray(dynamic_array* container)
{
    printf("Array elements: ");
    for (int i = 0; i < container->size; i++) {
        printf("%d ", container->array[i]);
    }
    printf("\nSize: ");
    printf("%ld", container->size);
    printf("\nCapacity: ");
    printf("%ld\n", container->capacity);
}

5. deleteItem()

This function will allow to delete of the delete operation using the remove element at the purticular index.

Code:

void deleteItem(dynamic_array* container, int index)
{
    if(index > container->size) {
        printf("Index Out of Bounds\n");
        return;
    }

    for (int i = index; i < container->size; i++) {
        container->array[i] = container->array[i + 1];
    }
    container->size--;
}

FAQ- Dynamically Growing Array in C