Bigger Example 3: Dynamic Array

UpdatedDecember 30, 2023

I am Jyotiprakash, a deeply driven computer systems engineer, software developer, teacher, and philosopher. With a decade of professional experience, I have contributed to various cutting-edge software products in network security, mobile apps, and healthcare software at renowned companies like Oracle, Yahoo, and Epic. My academic journey has taken me to prestigious institutions such as the University of Wisconsin-Madison and BITS Pilani in India, where I consistently ranked among the top of my class.

At my core, I am a computer enthusiast with a profound interest in understanding the intricacies of computer programming. My skills are not limited to application programming in Java; I have also delved deeply into computer hardware, learning about various architectures, low-level assembly programming, Linux kernel implementation, and writing device drivers. The contributions of Linus Torvalds, Ken Thompson, and Dennis Ritchie—who revolutionized the computer industry—inspire me. I believe that real contributions to computer science are made by mastering all levels of abstraction and understanding systems inside out.

In addition to my professional pursuits, I am passionate about teaching and sharing knowledge. I have spent two years as a teaching assistant at UW Madison, where I taught complex concepts in operating systems, computer graphics, and data structures to both graduate and undergraduate students. Currently, I am an assistant professor at KIIT, Bhubaneswar, where I continue to teach computer science to undergraduate and graduate students. I am also working on writing a few free books on systems programming, as I believe in freely sharing knowledge to empower others.

Comments

Join the discussion

No comments yet. Be the first to comment.

C Programming

Part 1 of 50

More from this blog

Computer Arithmetic: From Fast Adders to Floating-Point

Arithmetic is the beating heart of every processor. Whether your machine is rendering 3-D graphics, training a neural network, or simply incrementing a loop counter, the ALU (Arithmetic Logic Unit) is doing the heavy lifting. In this deep-dive, I wan...

Feb 12, 202629 min read

The Complete Memory Hierarchy: From Semiconductor RAM to Virtual Memory

The performance gap between processors and main memory has been widening for decades. Modern processors can execute billions of instructions per second, but accessing data from main memory takes hundreds of processor cycles. This disparity creates a ...

Jan 7, 202670 min read

The Ultimate Spring Boot Guide: From Fundamentals to Production-Ready REST APIs

Introduction Welcome to the most comprehensive Spring Boot guide you'll find! This isn't just another tutorial that skims the surface. We're going to dive deep into every concept, explain every annotation, walk through every line of code, and underst...

Dec 26, 2025125 min read

Understanding Functions, Memory, and Pointers in C: A Complete Guide

Part 1: Functions and the Call Stack Before we can understand pointers and memory management in C, we need to understand how functions work and what happens behind the scenes when your program runs. This foundation will make everything else click int...

Dec 16, 202583 min read

Datapath and Control

The Basic Processing Unit is the brain of every computer. It fetches instructions from memory, decodes them, and executes the operations they specify. Whether you're running a simple addition or a complex algorithm, every operation flows through this...

Dec 10, 202534 min read

Jyotiprakash's Blog

251 posts

I'm Jyotiprakash, a software dev and professor at KIIT, with expertise in system programming.

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

Initialization with an initial capacity.
Accessing an element at a given index.
Setting the value at a given index.
Inserting a new element at a specific index (with automatic capacity adjustment if necessary).
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.

Command Palette

Comments

C Programming

More from this blog

1. Structure Definition:

2. Function Prototypes:

3. initDynamicArray Function:

4. get and set Functions:

5. insert Function:

6. removeAt Function:

7. resizeIfNeeded Function:

8. main Function: