Array Insertion and Deletion with C++ Examples

A static array is helpful for faster access, but it is inefficient for insertion/deletion operations. This can be the preferred choice in the following scenarios.

• Applications always operate with a smaller amount of data.
• Requires frequent access to the data while having minimal insertion/deletion operations.
• Also, use the static array if the Insertion and deletion operations always occur at the last position.

1. Representation

// Mmaximum capacity
#define CAPACITY 10

// Array data
int array[CAPACITY];
    
// Number of elements currently stored in Array
int size = 0;

2. C++ Example for Array Insertion and Deletion

/**
 * C++ example to demonstrate Array data structure
 */
#include <iostream>
using namespace std;

// Mmaximum capacity
#define CAPACITY 10

/**
 * Array implementation
 */
class Array
{
    // Array data
    int array[CAPACITY];
    
    // Size of the array
    int size;
    
public:
    // Constructor
    Array() : size(0) {}
    
    // Insert an element into the given position
    void insert_at(int element, int pos);
    
    // Delete an element by the given position
    void delete_at(int pos);
    
    // Search the given element and return the position
    // Returns the index if found, -1 otherwise.
    int search(int element);
    
    // Access the element at given position
    // Returns the element
    int get(int pos);
    
    // Traverse and print the elements
    void traverse(const std::string& msg);
};

void Array::insert_at(int element, int pos)
{
    // Step 1. Check if the Array is full. If true, return error.
    if (size >= CAPACITY) {
        throw std::runtime_error("array capacity reached");
    }
    
    // Step 2. Check if the given position is out of data range. If true, return error.
    // Allow to insert at the end of array anyway.
    if (pos < 0 || pos > size) {
        throw std::runtime_error("position out of insertion range");
    }
    
    // Step 3. Free up the space for the new element by shifting the elements to next position.
    for (int i=size ; i > pos ; --i) {
        array[i] = array[i-1];
    }
    
    // Step 4. Insert the new element at the given position
    array[pos] = element;
    
    // Step 5. Increment the size by 1
    ++size;
}

void Array::delete_at(int pos)
{
    // Step 1. Check if the given position is out of data range. If true, return error.
    if (pos < 0 || pos >= size) {
        throw std::runtime_error("position out of data range");
    }
    
    // Step 2. Delete the element by shifting the elements to previous position.
    for (int i=pos; i < (size-1); ++i) {
        array[i] = array[i+1];
    }
    
    // Step 3. Decrement the size by 1
    --size;
}

int Array::search(int element)
{
    // Step 1. Traverse the array from the first position
    for (int i=0; i < size; i++) {
        // Step 2. Check if the element exists in the position. If true, return the position.
        if (array[i] == element) {
            return i;
        }
    }
    // Step 3. If the element is not found after the traversal, return -1
    return -1;
}

int Array::get(int pos)
{
    // Step 1. Check if the given position is out of array range. If true, return error.
    if (pos < 0 || pos >= size) {
        throw std::runtime_error("position out of data range");
    }
    
    // Step 2. Return the element at the given position
    return array[pos];
}

void Array::traverse(const std::string& msg)
{
    cout << msg << endl;
    cout << "[";
    for (int i=0; i < size; i++) {
        cout << "  " << array[i];
    }
    cout << "  ]" << endl;
}

int main()
{
    // Creating an Array
    Array arr;
    
    // Insert elements
    arr.insert_at(0, 0);
    arr.traverse("Array after insert_at(0, 0)");
    //==> [ 0 ]
    
    arr.insert_at(10, 1);
    arr.traverse("Array after insert_at(10, 1)");
    //==> [ 0, 10 ]
    
    arr.insert_at(20, 2);
    arr.traverse("Array after insert_at(20, 2)");
    //==> [ 0, 10, 20 ]
    
    arr.insert_at(5, 1);
    arr.traverse("Array after insert_at(5, 1)");
    //==> [ 0, 5, 10, 20 ]
    
    arr.insert_at(15, 3);
    arr.traverse("Array after insert_at(15, 3)");
    //==> [ 0, 5, 10, 15, 20 ]
    
    cout << "Access element at index 3 = " << arr.get(3) << endl;
    
    cout << "Searching element 5 found at index = " << arr.search(5) << endl;
    
    // Delete elements
    arr.delete_at(1);
    arr.traverse("Array after delete_at(1)");
    //==> [ 0, 10, 15, 20 ]
    
    arr.delete_at(2);
    arr.traverse("Array after delete_at(2)");
    //==> [ 0, 10, 20 ]
    
    return 0;
}

Output

Array after insert_at(0, 0)
[  0  ]
Array after insert_at(10, 1)
[  0  10  ]
Array after insert_at(20, 2)
[  0  10  20  ]
Array after insert_at(5, 1)
[  0  5  10  20  ]
Array after insert_at(15, 3)
[  0  5  10  15  20  ]
Access element at index 3 = 15
Searching element 5 found at index = 1
Array after delete_at(1)
[  0  10  15  20  ]
Array after delete_at(2)
[  0  10  20  ]

3. Operations of static Array

3.1. Insertion at the specific index

Algorithm

1. Check if the Array is full. If true, return the error.
2. Check if the given position is out of the data range. If true, return the error.
3. Free up the space for the new element by shifting elements to the next position.
4. Insert the new element at the given position
5. Increment the size by 1

Examples

An example workflow is provided here to insert the elements in an empty array with a capacity of 10. The array size is initially 0 for the empty array and will be incremented during insertion.

1. Insert element 0 at index 0

• The array is empty at this stage, so insert directly at index 0.

2. Insert element (10) at index 1

• No other elements are present at the requested index 1, so insert the element directly.

3. Insert element (20) at index 2

• Repeat the same workflow since no other elements are present at the requested index 2.

4. Insert element (5) at index 1

• The insertion is requested for index 1, but this is already occupied.
• Hence, free up the index by shifting elements 10 and 20 to one position right.
• Finally, insert the new element at index 1.

5. Insert element (15) at index 3

• The insertion is requested for index 3, but this is already occupied.
• Hence, free up the index by shifting element 20 to one position right.
• Finally, insert the new element at index 3.

3.2. Deletion at the specific index

Algorithm

1. Check if the given position is out of the data range. If true, return the error.
2. Delete the element by shifting elements to the previous position.
3. Decrement the size by 1

Examples

The following example illustrates the delete operations in the following array.

1. Delete the element at index 1

• Index 1 is located in the middle since there are elements at indexes 2, 3, and 4.
• Hence shift the elements at indexes 2, 3, and 4 to one position left.
• The element at index (1) is now replaced.

2. Delete the element at index 2

• Index 2 is located in the middle since there is an element at index 3.
• Hence shift the element at index 3 to one position left.
• The element at index (2) is now replaced.

3. Delete the new element at index 2

• The shifting is not required since index 2 is the last element now.
• The element at index (2) is deleted by simply reducing the array size by 1.

3.3. Search an element in the Array

Algorithm

1. Traverse the array from the first position
2. Check if the element exists in the position. If true, return the position.
3. If the element is not found after the traversal, return -1

Examples

Searching for an element in the array requires a linear search. So, we need to iterate the array from index 0 to the array size. Return the index once the element is found.

1. Seach for element (10)

• Iterate the array from index 0 and look for the element.
• So, searching the element (10) returns index 2.

4. References

• Array Data Structure: Types, Operations, and Applications
• Array Data Structure Wiki