Inserting an element into Array Data Structure

While working with arrays, for efficiency purposes, we allocate more space for an array than the required amount during initialization, leaving room for future expansion. Later on when there is a necessity, more elements are inserted into the array. At a low level, this insertion of new elements into an existing array is not straightforward and in this article we cover all possible insertion scenarios.

Note that the reason for this article is just to explain how insertion operation is done for arrays at a low level. Many programming languages have high level functions/methods which allows you to directly insert an element with a function call. For example in python you can do something like array.insert(position, element). You may try using them if the use case is simple does not require more efficient insert operations.

In all the scenarios discussed below, we take example of an Array with allocated size 7, but only 5 are stored in it. A variable maxLength to store the maximum number of elements the array can store and usedLength variable to store the actual number of elements stored in the array.

myArray = [1, 2, 3, 4, 5, _, _]

Insertion at the end of Array

In this scenario, the goal is to insert a new element immediately after the last element stored in the array. This is the simplest of all scenarios as movement of other elements present in the array is not required. We simply need to add the new element after the last element stored in the array and then increase the usedLength variable by 1.


#include <stdio.h>

int main() {
    // An array which can store 7 elements but only 5 are used
    int myArray[] = {1, 2, 3, 4, 5, 0, 0};
    
    // Initialize maximum number of elements the array can store
    int maxLength = sizeof(myArray) / sizeof(myArray[0]);

    // Initialze used length of the array
    int usedLength = 5;

    // Check if there is space for a new element
    if(usedLength < maxLength){
        // Compute index of the last element stored in the array
        int lastIndex = usedLength - 1;
        // Add a new element after the last index
        myArray[lastIndex + 1] = 6;
        // Increase the used length of the array
        usedLength = usedLength + 1;
    }
    else{
        // Array is full!!
    }

    // Now the array is {1, 2, 3, 4, 5, 6, 0}

    return 0;
}


# An array which can store 7 elements but only 5 are used
my_array = [1, 2, 3, 4, 5, 0, 0]

# Initialize maximum number of elements the array can store
max_length = len(my_array)

# Initialize used length of the array
used_length = 5

# Check if there is space for a new element
if used_length < max_length:
    # Compute index of the last element stored in the array
    last_index = used_length - 1
    # Add a new element after the last index
    my_array[last_index + 1] = 6
    # Increase the used length of the array
    used_length = used_length + 1
else:
    # Array is full!!
    pass

# Now the array is [1, 2, 3, 4, 5, 6, 0]


// An array which can store 7 elements but only 5 are used
let myArray = [1, 2, 3, 4, 5, 0, 0];

// Initialize maximum number of elements the array can store
let maxLength = myArray.length;

// Initialize used length of the array
let usedLength = 5;

// Check if there is space for a new element
if (usedLength < maxLength) {
    // Compute index of the last element stored in the array
    let lastIndex = usedLength - 1;
    // Add a new element after the last index
    myArray[lastIndex + 1] = 6;
    // Increase the used length of the array
    usedLength = usedLength + 1;
} else {
    // Array is full!!
}

// Now the array is [1, 2, 3, 4, 5, 6, 0]


public class Main {
    public static void main(String[] args) {
        // An array which can store 7 elements but only 5 are used
        int[] myArray = {1, 2, 3, 4, 5, 0, 0};

        // Initialize maximum number of elements the array can store
        int maxLength = myArray.length;

        // Initialize used length of the array
        int usedLength = 5;

        // Check if there is space for a new element
        if (usedLength < maxLength) {
            // Compute index of the last element stored in the array
            int lastIndex = usedLength - 1;
            // Add a new element after the last index
            myArray[lastIndex + 1] = 6;
            // Increase the used length of the array
            usedLength = usedLength + 1;
        } else {
            // Array is full!!
        }

        // Now the array is {1, 2, 3, 4, 5, 6, 0}
    }
}

Insertion at the start of Array

In this scenario, the goal is to insert a new element before the first element in the array. Since all the elements stored in the array are present in continuous memory locations, there is no gap at the beginning. So we can’t just add the new element directly.

When you want to insert a new element at the beginning of an array, you need to make room for it by shifting all the existing elements one position to the right. This movement effectively creates an empty slot at the start of the array, allowing you to place the new element at the beginning, ensuring that none of the existing data is overwritten.

Below is an example illustration on how this process looks:

// Shift all elements one position right
[1, 2, 3, 4, 5, _, _]
[1, 2, 3, 4, _, 5, _]
[1, 2, 3, _, 4, 5, _]
[1, 2, _, 3, 4, 5, _]
[1, _, 2, 3, 4, 5, _]
[_, 1, 2, 3, 4, 5, _]
// Now Insert a new element at the beginning
[6, 1, 2, 3, 4, 5, _]

Below is the code for inserting an element at the start of an array:


#include <stdio.h>

int main() {
    int myArray[] = {1, 2, 3, 4, 5, 0, 0};
    int maxLength = sizeof(myArray) / sizeof(myArray[0]);
    int usedLength = 5;

    // Check if there is space for a new element
    if (usedLength < maxLength) {
        // Shift existing elements to the right
        for (int i = usedLength; i > 0; i--) {
            myArray[i] = myArray[i - 1];
        }

        // Insert the new element at the start
        myArray[0] = 6;

        // Increase the used length of the array
        usedLength = usedLength + 1;
    } else {
        // Array is full!!
    }

    // Now the array is {6, 1, 2, 3, 4, 5, 0}

    // Print the updated array
    printf("Updated Array: ");
    for (int i = 0; i < usedLength; i++) {
        printf("%d ", myArray[i]);
    }

    return 0;
}


my_array = [1, 2, 3, 4, 5, 0, 0]
max_length = len(my_array)
used_length = 5

# Check if there is space for a new element
if used_length < max_length:
    # Shift existing elements to the right
    for i in range(used_length, 0, -1):
        my_array[i] = my_array[i - 1]

    # Insert the new element at the start
    my_array[0] = 6

    # Increase the used length of the array
    used_length = used_length + 1
else:
    # Array is full!!
    pass

# Now the array is [6, 1, 2, 3, 4, 5, 0]

# Print the updated array
print("Updated Array:", my_array[:used_length])


let myArray = [1, 2, 3, 4, 5, 0, 0];
let maxLength = myArray.length;
let usedLength = 5;

// Check if there is space for a new element
if (usedLength < maxLength) {
    // Shift existing elements to the right
    for (let i = usedLength; i > 0; i--) {
        myArray[i] = myArray[i - 1];
    }

    // Insert the new element at the start
    myArray[0] = 6;

    // Increase the used length of the array
    usedLength = usedLength + 1;
} else {
    // Array is full!!
}

// Now the array is [6, 1, 2, 3, 4, 5, 0]


public class Main {
    public static void main(String[] args) {
        int[] myArray = {1, 2, 3, 4, 5, 0, 0};
        int maxLength = myArray.length;
        int usedLength = 5;

        // Check if there is space for a new element
        if (usedLength < maxLength) {
            // Shift existing elements to the right
            for (int i = usedLength; i > 0; i--) {
                myArray[i] = myArray[i - 1];
            }

            // Insert the new element at the start
            myArray[0] = 6;

            // Increase the used length of the array
            usedLength = usedLength + 1;
        } else {
            // Array is full!!
        }

        // Now the array is {6, 1, 2, 3, 4, 5, 0}

        // Print the updated array
        System.out.print("Updated Array: ");
        for (int i = 0; i < usedLength; i++) {
            System.out.print(myArray[i] + " ");
        }
    }
}

Insertion at any given position in the Array

In this scenario, the goal is to insert a new element at any given index in the array. All the existing elements to the right of insert index needs to be moved one position to the right. This operation creates a vacancy at insert index and new element can be added to that index.

Below is an example illustration on how this process looks for inserting a new element at index 2:

// Shift all elements from index 2 to one position right
[1, 2, 3, 4, 5, _, _]
[1, 2, 3, 4, _, 5, _]
[1, 2, 3, _, 4, 5, _]
[1, 2, _, 3, 4, 5, _]
// Now Insert a new element at index 2 which is vacant
[1, 2, 6, 3, 4, 5, _]

Below is the code for inserting an element at a given position in the array:


#include <stdio.h>

int main() {
    int myArray[] = {1, 2, 3, 4, 5, 0, 0};
    int maxLength = sizeof(myArray) / sizeof(myArray[0]);
    int usedLength = 5;
    int insertIndex = 2; // Index at which to insert the new element
    int newValue = 6;   // Value to be inserted
    
    // Check if there is space
    if (usedLength < maxLength) {
        // Shift all elements from insertIndex to the right
        for (int i = usedLength; i > insertIndex; i--) {
            myArray[i] = myArray[i - 1];
        }

        // Insert the new element at the specified index
        myArray[insertIndex] = newValue;

        // Increase the used length of the array
        usedLength++;
    } else {
        printf("Array is full!\n");
    }

    // Print the updated array
    printf("Updated Array: ");
    for (int i = 0; i < usedLength; i++) {
        printf("%d ", myArray[i]);
    }

    return 0;
}


my_array = [1, 2, 3, 4, 5, 0, 0]
max_length = len(my_array)
used_length = 5
insert_index = 2  # Index at which to insert the new element
new_value = 6    # Value to be inserted

# Check if there is space
if used_length < max_length:
    # Shift all elements from insertIndex to the right
    for i in range(used_length, insert_index, -1):
        my_array[i] = my_array[i - 1]

    # Insert the new element at the specified index
    my_array[insert_index] = new_value

    # Increase the used length of the array
    used_length += 1
else:
    print("Array is full")


let myArray = [1, 2, 3, 4, 5, 0, 0];
let maxLength = myArray.length;
let usedLength = 5;
let insertIndex = 2;  // Index at which to insert the new element
let newValue = 6;    // Value to be inserted

// Check there is space
if (usedLength < maxLength) {
    // Shift all elements from insertIndex to the right
    for (let i = usedLength; i > insertIndex; i--) {
        myArray[i] = myArray[i - 1];
    }

    // Insert the new element at the specified index
    myArray[insertIndex] = newValue;

    // Increase the used length of the array
    usedLength += 1;
} else {
    console.log("Array is full.");
}


public class Main {
    public static void main(String[] args) {
        int[] myArray = {1, 2, 3, 4, 5, 0, 0};
        int maxLength = myArray.length;
        int usedLength = 5;
        int insertIndex = 2; // Index at which to insert the new element
        int newValue = 6;   // Value to be inserted

        // Check if there is space
        if (usedLength < maxLength) {
            // Shift all elements from insertIndex to the right
            for (int i = usedLength; i > insertIndex; i--) {
                myArray[i] = myArray[i - 1];
            }

            // Insert the new element at the specified index
            myArray[insertIndex] = newValue;

            // Increase the used length of the array
            usedLength += 1;
        } else {
            System.out.println("Array is full.");
        }

        // Print the updated array
        System.out.print("Updated Array: ");
        for (int i = 0; i < usedLength; i++) {
            System.out.print(myArray[i] + " ");
        }
    }
}

Please note that for ease of understanding, insert index value is not validated before performing the insert. Ideally a check needs to be added to make sure that insert index is valid i.e, insertIndex >= 0 && insertIndex <= usedLength. Where insertIndex is the index where we wish to insert a new element and usedLength indicates the index after the last element in the array.

Conclusion

For all the scenarios, this is how the algorithm looks like:

Determine the index at which you want to insert the new element.
Starting from the index to insert, shift all the existing elements one position to the right
Insert the new element into the array at the required index.