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.
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:
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:
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.