Deletion in array means removing an element and replacing it with the next element or element present at next index. It involves three cases
Deletion in Array- an element at the beginning of the array
In this case we have to move all the elements one position forward to fill the position of the element at the beginningof array. Though the deletion process is not difficult but moving all elements one position forward involve movement of all the existing elements except the one being deleted. This is the worst case scenario in deletion in a linear array.
In the example array elements from index 1 to index 8 have to moved one position forwards so that the first element is replaced by second, second by third and so on
Deletion in Array – an element at the end of the array
In this case we don’t have to move any elements since the action here will be just removing the last element. This is done by redefining the index of last element of linear array = N-1. This is the best case scenario in deletion in a linear array.
In the example array no elements are moved. The last element is removed by setting the index of last element as 7
Deletion in Array – an element at the give position J
Let J be any location in the array for one existing element. We have to delete the element at J position. To do this starting from J every element is moved one place forward so that the element after index J comes to position of Jth element. This is the average case scenario in deletion in linear array.
In the example array ,elements from index J (4) to index 8 have to moved one position forward so that an element at index 4 is replaced by element at index 5. Similarly element at 6th postion comes at 5th position, element at 7th position comes at 6th position and element at 8th position replaces element at 7th position completing the deletion process
Note:- for any one of these three cases the count of elements decreases by 1
Algorithm for Element Deletion in Array
Algorithm DeleteLA (DATA, N, ITEM, LOC) Desc: This algorithm deletes an element at Jth position in a linear array DATA with N elements and stores in ITEM If LOC=1 it means the element to be deleted is at the beginning If LOC =N it means the element be deleted is at the end If LOC = J it means the elements have to be deleted is at at Jth Location Begin Step 1: [Initialize counter I with index of element to be deleted] I=J Step 2: [Store the element to be deleted in ITEM] ITEM=DATA[J] Step 3: While I<N repeat steps 4 and 5 Step 4: [Move the current element one position forward] DATA[I]=DATA[I+1] Step 5: [Increment counter I] I=I+1 Step 6: [Update total under of array elements] N=N-1 Exit
Complexity of Deletion in Array Algorithm
Deletion operation results deleting one element of a linear array . In the algorithm the following is the way the steps are counted.
- Steps 1, 2 and 6 are executed once, so they contributes 3 to complexity function f(n)
- Step 3 is a loop control step that executes step 4 and step 5 N times (once for each element of array DATA after the element to be deleted)
So the f(n) can be defined as
f(n)= 2*n+3 or
The highest order term in this function defined in the terms of input size of the algorithm is n, so we can say that the complexity of this algorithm is O(n). It also means that the average time of element deletion in array grows linearly with the size of array DATA.