Data Structures and Algorithms
In this tutorial we will learn to delete elements from an Array data structure in different positions.
We can delete an element from the end, beginning and in between.
In order to delete an element from the end of an array of a given SIZE
, we will maintain a variable END
that will always point to the last element of the array. If there is no element in the array then END will be set to -1
and we will not perform deletion. If there are elements in the array then END will be greater than -1 hence we can set the element at index END to some random value (optional) and then decrement END by 1.
Time complexity will be O(1).
Before
arr = 1 2 3 4 5
^
END
Delete last element. Decrement END by 1.
After
arr = 1 2 3 4 0
^
END
We we delete from the beginning of the array i.e., index 0 then we move all the elements on the right side of index 0 by 1 position to the left and we decrement the END variable by 1 so that it points to the correct last position.
Time complexity will be O(n).
Before
arr = 1 2 3 4 5
^ ^
DELETE END
Move all the elements one position left. Decrement END by 1.
After
arr = 2 3 4 5 0
^
END
When deleting an element at index I
we have to left shift all the elements on the right side of index I
by one position and then decrement the END
variable by 1.
Time complexity will be O(n).
Before
arr = 1 2 3 4 5
^ ^
DELETE END
Move all the elements one position left. Decrement END by 1.
After
arr = 1 2 4 5 0
^
END
In the following C++ example we are going to demonstrate deletion of an element from an array.
#include <iostream>
using namespace std;
const int SIZE = 5;
int arr[SIZE];
int END = -1;
void freshInsertElements()
{
cout << "REFRESH!" << endl;
cout << "Inserting " << SIZE << " elements in the array arr..." << endl;
int i;
for (i = 0; i < SIZE; i++)
{
arr[i] = i + 1;
}
END = SIZE - 1;
}
void print()
{
cout << "Printing the content of array arr..." << endl;
int i;
for (i = 0; i <= END; i++)
{
cout << "arr[" << i << "] = " << arr[i] << endl;
}
cout << endl;
}
void deleteFromEnd()
{
cout << "Delete from end" << endl;
END--;
}
void deleteFromBeginning()
{
cout << "Delete from beginning" << endl;
int i;
for (i = 1; i <= END; i++)
{
arr[i - 1] = arr[i];
}
END--;
}
void deleteIndex(int index)
{
cout << "Delete element at index " << index << "." << endl;
int i;
for (i = index + 1; i <= END; i++)
{
arr[i - 1] = arr[i];
}
END--;
}
int main(void)
{
freshInsertElements();
print();
deleteFromEnd();
print();
freshInsertElements();
print();
deleteFromBeginning();
print();
freshInsertElements();
print();
deleteIndex(3);
print();
return 0;
}
Output
REFRESH!
Inserting 5 elements in the array arr...
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5
Delete from end
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
REFRESH!
Inserting 5 elements in the array arr...
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5
Delete from beginning
Printing the content of array arr...
arr[0] = 2
arr[1] = 3
arr[2] = 4
arr[3] = 5
REFRESH!
Inserting 5 elements in the array arr...
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5
Delete element at index 3.
Printing the content of array arr...
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 5
ADVERTISEMENT