Inserting into an array

Inserting an element into an Array is a very common operation. It is also a very important operation because it is the basis for many other Array operations. In this article, we will discuss some interesting aspects of inserting an element into an Array.

Inserting a new element into an Array can take many forms:

1. Inserting a new element at the end of the Array.
2. Inserting a new element at the beginning of the Array.
3. Inserting a new element at any given index inside the Array.

Inserting at the End of an Array

Inserting an element at the end of an Array is the most common operation. It is also the easiest operation to implement. All you need to do is check if the Array is full, and if it is not, then you can insert the new element at the end of the Array.

Here is the code for inserting an element at the end of an Array.

Inserting at the End of an Array

// Create a new array with a capacity of 6.
int[] array = new int[6];

// Current length is 0, because it has 0 elements.
int length = 0;

// Add 5 items into it.
for (int i = 0; i < 5; i++) {
    array[i] = i * i;
    // Each time we add an element, the length goes up by one.
    length++;
}

// Check if the Array is full.
if (length < array.length) {
    // Insert the new element at the end of the Array.
    array[length] = length * length;
    // Increase the length by one.
    length++;
}

System.out.println("The Array has a capacity of " + array.length); // 6
System.out.println("The Array has a length of " + length); // 6

Inserting at the Start of an Array

Inserting an element at the start of an Array is a bit more complicated than inserting an element at the end of an Array. The reason is that when you insert an element at the start of an Array, you need to shift all the elements to the right by one position. This is because you need to make room for the new element. In fact, the time taken for insertion at the beginning of an Array will be proportional to the length of the Array. In terms of time complexity analysis, this is a linear time complexity: $O(N)$, where $N$ is the length of the Array.

Here's what this looks like in code.

Inserting at the Start of an Array

// Create a new array with a capacity of 6.
int[] array = new int[6];

// Current length is 0, because it has 0 elements.
int length = 0;

// Add 5 items into it.
for (int i = 0; i < 5; i++) {
    array[i] = i * i;
    // Each time we add an element, the length goes up by one.
    length++;
}

// Check if the Array is full.
if (length < array.length) {
    // Insert the new element at the start of the Array.
    // Shift all the elements to the right by one position.
    for (int i = length; i > 0; i--) {
        array[i] = array[i - 1];
    }
    // Insert the new element at the start of the Array.
    array[0] = length * length;
    // Increase the length by one.
    length++;
}

System.out.println("The Array has a capacity of " + array.length); // 6
System.out.println("The Array has a length of " + length); // 6

Inserting at any given index inside the Array

Inserting an element at any given index inside the Array is a bit more complicated than inserting an element at the start of an Array. The reason is that when you insert an element at any given index inside the Array, you need to shift all the elements to the right by one position. This is because you need to make room for the new element.

Again, this is also a costly operation since we could potentially have to shift almost all the other elements to the right before actually inserting the new element. As your saw above, shifting lots of elements one place to the right adds to the time complexity of the insertion task.

Here's what this looks like in code.

Inserting at any given index inside the Array

// Create a new array with a capacity of 6.
int[] array = new int[6];

// Current length is 0, because it has 0 elements.
int length = 0;

// this is the index where we want to insert the new element.
int index = 2;

// Add 5 items into it.
for (int i = 0; i < 5; i++) {
    array[i] = i * i;
    // Each time we add an element, the length goes up by one.
    length++;
}

// Check if the Array is full.
if (length < array.length) {
    // Insert the new element at the start of the Array.
    // Shift all the elements to the right by one position.
    for (int i = length; i > index; i--) {
        array[i] = array[i - 1];
    }
    // Insert the new element at the start of the Array.
    array[index] = length * length;
    // Increase the length by one.
    length++;
}

System.out.println("The Array has a capacity of " + array.length); // 6
System.out.println("The Array has a length of " + length); // 6