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] = 3Time 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] = 5Time 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 4In 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] = 4Time 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] = 5Time 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] = 4Time complexity is O(n).
ADVERTISEMENT