Array - Insertion

Insertion means inserting an element in our data structure.

We can perform insertion in three ways they are-

1. Insertion at beginning.

2. Insertions end.

3. Insertion at Kth position

Insertion at beginning

Inserting an element at the beginning of an array, let's see how it happens:

Pseudocode -

function insertAtBeginning(arr, element, size):
    // Shift elements to make space for the new element
    for i from size down to 1:
        arr[i] = arr[i-1]

    // Insert the new element at the beginning
    arr[0] = element

Program -

#include <iostream>
using namespace std;

void insertAtBeginning(int arr[], int& size, int element) {
    // Shift elements to make space for the new element
    for (int i = size; i > 0; i--) {
        arr[i] = arr[i - 1];
    }

    // Insert the new element at the beginning
    arr[0] = element;
    size++; // Increase the size after insertion
}

int main() {
    int arr[100]; // Assuming an array of size 100
    int size = 10; // Current size of the array
    int element = 42; // Element to be inserted

    insertAtBeginning(arr, size, element);

    // Print the updated array
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

Time and Space Complexity

Time Complexity: The time complexity for inserting an element at the beginning of an array is O(n) because, in the worst case, you need to shift all existing elements to make space for the new element.

Space Complexity: The space complexity for this operation is O(1) because it uses a constant amount of additional space regardless of the size of the array.

Insertion at end

Inserting an element at the end of an array in C++ involves a few steps. Below is the pseudocode, program, and the analysis of time and space complexity:

Pseudocode -

Function insertAtEnd(arr, size, element):
    if size is less than the capacity of the array:
        arr[size] = element
        size = size + 1
    else:
        print "Array is full, cannot insert element."

Program -

#include <iostream>
using namespace std;

void insertAtEnd(int arr[], int &size, int element, int capacity) {
    if (size < capacity) {
        arr[size] = element;
        size++;
    } else {
        cout << "Array is full, cannot insert element." << endl;
    }
}

int main() {
    const int capacity = 10; // Capacity of the array
    int arr[capacity] = {1, 2, 3, 4, 5};
    int size = 5; // Current size of the array

    int elementToInsert = 10;
    insertAtEnd(arr, size, elementToInsert, capacity);

    // Print the updated array
    cout << "Updated Array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

Time and Space Complexity

Time Complexity: The time complexity for inserting an element at the end of an array is O(1) on average. This is because the operation involves accessing a specific index (the end of the array) and assigning a value. However, if resizing is required (when the array is full), the time complexity would be O(n), where n is the current size of the array, as all elements need to be copied to a new larger array.

Space Complexity: The space complexity for inserting an element at the end of an array is O(1). This is because the operation does not use any additional space that scales with the input size; it only modifies the existing array.

Insertion at Kth position

Insertion at kth position in an array involves adding an element at the specified index in the array. Below is the pseudocode and a simple C++ program for insertion at the kth position, along with the time and space complexity analysis:

Pseudocode -

Function InsertAtKthPosition(arr, size, k, element):
    // Check if the array is full
    if size is equal to the capacity of the array:
        return "Array is full, insertion not possible"

    // Check if k is a valid index
    if k < 0 or k > size:
        return "Invalid index for insertion"

    // Shift elements to make space for the new element
    for i from size - 1 to k:
        arr[i + 1] = arr[i]

    // Insert the new element at the kth position
    arr[k] = element

    // Increment the size of the array
    size = size + 1

    return "Element inserted successfully"

Program -

#include <iostream>

using namespace std;

void insertAtKthPosition(int arr[], int &size, int k, int element) {
    // Check if the array is full
    if (size == sizeof(arr) / sizeof(arr[0])) {
        cout << "Array is full, insertion not possible" << endl;
        return;
    }

    // Check if k is a valid index
    if (k < 0 || k > size) {
        cout << "Invalid index for insertion" << endl;
        return;
    }

    // Shift elements to make space for the new element
    for (int i = size - 1; i >= k; i--) {
        arr[i + 1] = arr[i];
    }

    // Insert the new element at the kth position
    arr[k] = element;

    // Increment the size of the array
    size++;

    cout << "Element inserted successfully" << endl;
}

int main() {
    const int capacity = 100;
    int arr[capacity] = {1, 2, 3, 4, 5};
    int size = 5;

    int k = 2; // Insert at the 2nd position
    int element = 10;

    insertAtKthPosition(arr, size, k, element);

    // Print the updated array
    cout << "Updated array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

Time and space complexity

Time Complexity: The time complexity of the insertion at the kth position is O(n), where n is the number of elements in the array. This is because, in the worst case, all the elements after the insertion point need to be shifted.

Space Complexity: The space complexity is O(1) because the algorithm uses a constant amount of additional space for variables, irrespective of the input size. The array size is fixed, and the space required for the operation is constant.