Data Structures and Algorithms
In this tutorial we will learn to insert new elements in an Array data structure in different positions.
We can insert a new element at the end of the array, at the beginning of the array and somewhere in between.
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).
Inserting at the beginning of an array has two possibilities.
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).
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).
This too has two possibilities.
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).
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