Array Insert Operation

Insertion Operation in Arrays

Insertion is an operation in arrays where a new element is added at a specific position.

Most programming languages have this functionality built-in. However, this class focuses on understanding what happens behind the scenes — how it works, what edge cases to consider, and the time and space complexities involved.

Visual Example

Initial Array:

Insert element 25 at index 2.

Desired Output

Step by step process

Given insert index is 2.

We have to shift the highlighted elements from index 2 to the right side by one position.

Elements from index 2 onward are shifted one position to the right.

Assign array element at index 2 with the given value 25.

Edge Cases for Array Insert Operation

Let’s look at some edge cases for the array insert operation. These examples may not cover every possible scenario, but they give a good idea of how to implement the insert function. Depending on the programming language you're using, you can explore more edge cases to fully complete the functionality.

Edge Case 1: Inserting into a Full Array (Fixed Size)

If the array has a fixed size (e.g., in C or Java), inserting into a full array is not possible without resizing or overwriting. This leads to overflow errors or failure to insert.

if size == capacity:
    raise Error("Array is full")

Edge Case 2: Inserting at the Start

To insert at the beginning, all elements must be shifted one position to the right to make space at index 0. This is an O(n) operation.

for i from size - 1 to 0:
    array[i + 1] = array[i]
array[0] = newElement
size++

Edge Case 3: Inserting at the End

This is typically the most efficient operation if the array has space. It appends the new element at the next available position.

if size == capacity:
    raise Error("Array is full")
array[size] = newElement
size++

Edge Case 4: Inserting in the Middle

When inserting in the middle, all elements from the given index to the end must be shifted to the right to create space.

for i from size - 1 to index:
    array[i + 1] = array[i]
array[index] = newElement
size++

Edge Case 5: Index Out of Bounds

If the index is less than 0 or greater than the current size, the insertion is invalid and should raise an error.

if index < 0 or index > size:
    raise Error("Index out of bounds")

Complete Pseudocode: Insert Element at Specific Position

Considering all the edge cases, let us write the pseudocode.

Keep the checks that we need to do before actually inserting the element at the start. Then handle the shifting mechanism, update any parameters like size, and finally return or display the resulting array if needed.

function insert(array, size, capacity, index, newElement):
    if index < 0 or index > size:
        raise Error("Index out of bounds")

    if size == capacity:
        raise Error("Array is full")

    for i from size - 1 to index:
        array[i + 1] = array[i]

    array[index] = newElement
    size++

    return array

Now, we will see this pseudocode in action using a Visualization Player in the following section.

For simplicity, we will only consider array, index, and newElement in the visualization.

function insert(array, size, capacity, index, newElement):
    if index < 0 or index > length(array):
        raise Error("Index out of bounds")

    if array is full:
        raise Error("Array is full")

    for i from size - 1 down to index:
        array[i + 1] = array[i]

    array[index] = newElement

    return array

Visualization Player

Insert Operation Examples

The following examples show how to insert an element at different positions in an array, like at the beginning, in the middle, or at the end.

Time Complexity of Array Insert Operation

Space Complexity of Array Insert Operation

Note:

• This logic is applicable for static arrays where size is predefined.
• In dynamic arrays (like Python lists), insertion can be handled more flexibly, but the underlying concept remains useful.

Key Takeaways

• Arrays require shifting elements to insert at the beginning or in the middle.
• Insertion at the end is efficient if space is available.
• Be mindful of array size and shifting logic when designing algorithms.