Array Insertion and Deletion

An array is the simplest data structure, and many programming languages provide arrays as a built-in feature. An array is a collection of a finite number of variables of the same type, and each variable in the array is called an element.

Creating an array reserves a contiguous block of memory in which data is stored in order. Each element has its own index, beginning at 0.

Reading an element is the simplest array operation. Because an array is stored sequentially in memory, an element can be read directly when its index is given. Reading by index in this way is called random access. Reading an array element has a time complexity of $O(1)$.

The disadvantage of arrays appears when inserting and deleting elements. Because array elements are stored contiguously and tightly in memory, insertion and deletion can force many elements to move and reduce efficiency. Overall, arrays are suitable for scenarios with many reads and few writes.

Inserting Elements

There are three cases when inserting an element into an array:

Tail Insertion

Place the inserted element directly in the free position at the end of the array.

Middle Insertion

First move the element at the insertion position and every following element backward to make room, then place the new element in that position.

Expansion

An array's length is fixed when it is created. To expand it, create a new array twice the length of the old array and copy all elements from the old array into it.

The best case for array insertion is tail insertion, which moves no elements and has a time complexity of $O(1)$. The worst case is insertion at the first position, which requires moving all following $n - 1$ elements and has a time complexity of $O(n)$.

array_t *array_add(array_t *arr, T elem) {
    if (arr == NULL) {
        return NULL;
    }

    if (arr->size == arr->capacity) {
        arr = resize(arr);
    }
    arr->data[arr->size++] = elem;
    return arr;
}

array_t *array_insert(array_t *arr, int index, T elem) {
    if (arr == NULL) {
        return NULL;
    }

    if (index < 0 || index > arr->size) {
        fprintf(stderr, "Error: index out of bound.\n");
        return arr;
    }

    if (arr->size == arr->capacity) {
        arr = resize(arr);
    }

    for (int i = arr->size - 1; i >= index; i--) {
        arr->data[i + 1] = arr->data[i];
    }
    arr->data[index] = elem;
    arr->size++;
    return arr;
}

Deleting Elements

Array deletion is the reverse of insertion. If the deleted element is in the middle of the array, every following element must move forward by one position.

T array_remove(array_t *arr, int index) {
    if (arr == NULL) {
        exit(1);
    }

    if (index < 0 || index >= arr->size) {
        fprintf(stderr, "Error: index out of bound.\n");
        exit(1);
    }

    T elem = arr->data[index];
    for (int i = index; i < arr->size - 1; i++) {
        arr->data[i] = arr->data[i + 1];
    }
    arr->size--;
    return elem;
}

Because array deletion involves moving elements, its time complexity is $O(n)$.