Data Structures - Arrays - Insertion

Data Structures and Algorithms

In this tutorial we will learn to insert new elements in an Array data structure in different positions.

Table of Content

Insertion

We can insert a new element at the end of the array, at the beginning of the array and somewhere in between.

Insert at the end

In order to insert an element at the end of the array we use the index of that empty position and then we assign the value to that empty position.

Let us say we have an array of SIZE 3.

We can maintain an END variable that will point to the last element in the array. Initially, when there is no element in the array, we will set END = -1.

If we want to insert an element at the end of the array, we will check if END + 1 is less than the SIZE of the array. If yes, then we insert the new element and increment END by 1. Otherwise, we prompt that the array is full.

Following C++ code will insert a new element at the end of the array.

#include <iostream>
using namespace std;

const int SIZE = 3;
int arr[SIZE];
int END = -1;

void insert(int value)
{
  if (END + 1 < SIZE)
  {
    arr[END + 1] = value;
    cout << "inserted " << value << " at index " << END + 1 << endl;
    END++;
  }
  else
  {
    cout << "Cannot insert " << value << "! Array is full" << endl;
  }
}

void print()
{
  cout << "Printing the content of array arr..." << endl;
  int i;
  for (i = 0; i < SIZE; i++)
  {
    cout << "arr[" << i << "] = " << arr[i] << endl;
  }
}

int main(void)
{
  insert(1);
  insert(2);
  insert(3);
  insert(4);

  print();

  return 0;
}

Output

inserted 1 at index 0
inserted 2 at index 1
inserted 3 at index 2
Cannot insert 4! Array is full
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3

Time complexity to insert an element at the end is O(1).

Insert at the beginning

Inserting at the beginning of an array has two possibilities.

  • Insert at index 0 without shifting other elements of the array to the right side.
  • Insert at index 0 and shift other elements of the array to the right side.

Insert without shifting

In the following C++ example we are inserting a new element at index 0 without shifting other elements. The size of the array is 5.

#include <iostream>
using namespace std;

const int SIZE = 5;
int arr[SIZE];
int END = -1;

void insert(int value)
{
  if (END + 1 < SIZE)
  {
    arr[END + 1] = value;
    cout << "inserted " << value << " at index " << END + 1 << endl;
    END++;
  }
  else
  {
    cout << "Cannot insert " << value << "! Array is full" << endl;
  }
}

void print()
{
  cout << "Printing the content of array arr..." << endl;
  int i;
  for (i = 0; i < SIZE; i++)
  {
    cout << "arr[" << i << "] = " << arr[i] << endl;
  }
}

int main(void)
{
  insert(1);
  insert(2);
  insert(3);
  insert(4);
  insert(5);

  print();

  arr[0] = 10;

  print();

  return 0;
}

Output

inserted 1 at index 0
inserted 2 at index 1
inserted 3 at index 2
inserted 4 at index 3
inserted 5 at index 4
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5
Printing the content of array arr...
arr[0] = 10
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5

Time complexity to insert at the beginning without shifting is O(1).

Insert with shifting

In this example we will first right shift (copy) all the elments by one position and then insert the new element at index 0. If the array is full then the last element will be overwritten by the second last element.

Before:
arr = 1 2 3 4 5

Insert 10 at the beginning and shift other elements.
arr[0] = 10

After:
10 1 2 3 4

In the following C++ example we are inserting a new element at index 0 and right shift all other elements.

#include <iostream>
using namespace std;

const int SIZE = 5;
int arr[SIZE];
int END = -1;

void insert(int value)
{
  if (END + 1 < SIZE)
  {
    arr[END + 1] = value;
    cout << "inserted " << value << " at index " << END + 1 << endl;
    END++;
  }
  else
  {
    cout << "Cannot insert " << value << "! Array is full" << endl;
  }
}

void print()
{
  cout << "Printing the content of array arr..." << endl;
  int i;
  for (i = 0; i < SIZE; i++)
  {
    cout << "arr[" << i << "] = " << arr[i] << endl;
  }
}

void insertAtBeginningWithRightShift(int value)
{
  int i;

  // first right shift
  for (i = END; i > 0; i--)
  {
    arr[i] = arr[i - 1];
  }

  // now insert
  arr[0] = value;

  cout << "Right shifted other elements and inserted " << value << " at index 0." << endl;
}

int main(void)
{
  insert(1);
  insert(2);
  insert(3);
  insert(4);
  insert(5);

  print();

  insertAtBeginningWithRightShift(10);

  print();

  return 0;
}

Output

inserted 1 at index 0
inserted 2 at index 1
inserted 3 at index 2
inserted 4 at index 3
inserted 5 at index 4
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5
Right shifted other elements and inserted 10 at index 0.
Printing the content of array arr...
arr[0] = 10
arr[1] = 1
arr[2] = 2
arr[3] = 3
arr[4] = 4

Time complexity to insert at the beginning and shifting other elements is O(n).

Insert at index

This too has two possibilities.

  • Insert at index I without shifting the right side elements one position to the right.
  • Insert at index I and shifting the right side elements one position to the right.

Insert at index I without shifting

In the following C++ example we are inserting at index I without right shifting other elements.

#include <iostream>
using namespace std;

const int SIZE = 5;
int arr[SIZE];
int END = -1;

void insert(int value)
{
  if (END + 1 < SIZE)
  {
    arr[END + 1] = value;
    cout << "inserted " << value << " at index " << END + 1 << endl;
    END++;
  }
  else
  {
    cout << "Cannot insert " << value << "! Array is full" << endl;
  }
}

void print()
{
  cout << "Printing the content of array arr..." << endl;
  int i;
  for (i = 0; i < SIZE; i++)
  {
    cout << "arr[" << i << "] = " << arr[i] << endl;
  }
}

int main(void)
{
  insert(1);
  insert(2);
  insert(3);
  insert(4);
  insert(5);

  print();

  arr[3] = 10;

  print();

  return 0;
}

Output

inserted 1 at index 0
inserted 2 at index 1
inserted 3 at index 2
inserted 4 at index 3
inserted 5 at index 4
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 10
arr[4] = 5

Time complexity is O(n).

Insert at index I and shift other elements

In the following example we will first right shift all the elements by one position starting from index I and then we will insert the new element at index I.

#include <iostream>
using namespace std;

const int SIZE = 5;
int arr[SIZE];
int END = -1;

void insert(int value)
{
  if (END + 1 < SIZE)
  {
    arr[END + 1] = value;
    cout << "inserted " << value << " at index " << END + 1 << endl;
    END++;
  }
  else
  {
    cout << "Cannot insert " << value << "! Array is full" << endl;
  }
}

void print()
{
  cout << "Printing the content of array arr..." << endl;
  int i;
  for (i = 0; i < SIZE; i++)
  {
    cout << "arr[" << i << "] = " << arr[i] << endl;
  }
}

void insertAtIndexWithRightShift(int index, int value)
{
  int i;

  // first right shift
  for (i = END; i > index; i--)
  {
    arr[i] = arr[i - 1];
  }

  // now insert
  arr[index] = value;

  cout << "Right shifted other elements and inserted " << value << " at index " << index << "." << endl;
}

int main(void)
{
  insert(1);
  insert(2);
  insert(3);
  insert(4);
  insert(5);

  print();

  insertAtIndexWithRightShift(3, 10);

  print();

  return 0;
}

Output

inserted 1 at index 0
inserted 2 at index 1
inserted 3 at index 2
inserted 4 at index 3
inserted 5 at index 4
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5
Right shifted other elements and inserted 10 at index 3.
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 10
arr[4] = 4

Time complexity is O(n).

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT