Insertion and Deletion in Arrays in Data Structure

Let A be a collection of data elements in the memory of the computer. “Inserting” refers to the operation of adding another element to the collection A, and “Deleting” refers to the operation of removing one of the elements from A.

Inserting an element at the ‘end’ of a linear array can be easily done. On the other hand, suppose we need to insert an element in the middle of the array. Then on the average, half of the elements must be moved downward to new locations to accommodate the new element and keep an order of the order of the other elements.


Similarly, deleting an element at the ‘end’ of an array presents no difficulties, but deleting an element somewhere in the middle of the array would require that each subsequent element is moved one location upward in order to ‘fill up’ the array.

(i) Algorithm: (Inserting into a linear array.)

INSERT (A, N, K, ITEM).
Here, A is a linear array with N elements and K is a positive integer such that K <= N. This algorithm inserts an element ITEM into the Kth position in A.

Step I: Set J:= N. [Initialize counter.]
Step II: Repeat steps 3 and 4 while J >= K:
Step III: Set A[J+1] := A[J]. [Move element downward.]
Step IV: J:= J-1. [Decrease counter.]
[End of step 2 loop.]
Step V: Set A[K] := ITEM. [Insert element.]
Step VI: Set N:= N+1. [Reset N.]
Step VII: Exit.

(i) Algorithm: (Deletion from a linear array.)

DELETE (A, K, N, ITEM). 

Here, A is a linear array with N elements and K is a positive integer such that K<= N. This algorithm deletes the Kth element from A.

Step I: Set ITEM:= A[K] and J:= K. [Initialize counter.]
Step II: Repeat steps 3 and 4 while J>N:
Step III: A[J] := A[J+1]. [Move element upward.]
Step IV: Set J:= J+1. [Increase counter.]
[End of step 2 loop.]
Step V: Set N:= N-1. [Reset N.]
Step VI: Exit.