Insert Algorithm

Introduction

The array insertion and shifting algorithm in Java is a fundamental technique for inserting an element into an array at a specific position while efficiently shifting the existing elements to accommodate the new addition.

This algorithm is essential for dynamically modifying the contents of an array and maintaining its integrity.

By leveraging this algorithm, developers can easily handle array insertions, ensuring optimal performance and maintaining the order of elements.

In this article, we will explore the implementation of the array insertion and shifting algorithm in Java, providing a step-by-step guide and a code example that demonstrates how to incorporate new elements into an array at desired positions seamlessly.

Insertion algorithms

Inserting an element at the start/middle of an array falls under array weaknesses, which might impact the performance if we are dealing with a massive array of elements as we need to shift the rest of the elements, which takes O(N) time unless we add new values at the end of the array, taking O(1) time. 

For example, consider an array of Characters { A, B, D, E, F } with indexes ranging from 0 to 4, and the length of the array being 5.

What happens if we insert a character C at index 2? or what happens we insert the character C at the last index?

We are inserting an element and not updating the index. Hence we need to shift the rest of the elements to make space for char C to insert it right index. Let us see both algorithms in practice. There are two insert positions we need to consider:

1. Inserting at the end.
2. Inserting at the start/middle.

1. Insert the item at the end

As explained in the "Overview of arrays" lesson. When we declare an array, we create an array containing all zeros.

// array of elements with capacity as 5
int[] values = new int[5]; // equivalent to `values = {0, 0, 0, 0, 0}`

All array values are defaulted to 0.

Let us use a variable currentLength to track the current items inserted in the array. Where currentLength points to the array's next index at any given time.

We use a simple snippet to insert elements into the array. We have inserted a value 200 at the end of the array(array length).

Illustration

The sketch looks like this: