Explain with examples: i) insertion and ii) deletion in an array

Insertion in an array

• Let A be a collection of data elements stored in the memory of the computer.
• Inserting refers to the operation of adding another element to the collection A.
• Inserting an element at the “end” of the linear array can be easily done provided the memory space allocated for the array is large enough to accommodate the additional element.
• Inserting an element in the middle of the array, then on average, half of the elements must be moved downwards to new locations to accommodate the new element and keep the order of the other elements.

Algorithm:
INSERT (LA, N, K, ITEM)
Here LA 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 LA.

1. [Initialize counter] set J:= N
2. Repeat step 3 and 4 while J ≥ K
3. [Move Jth element downward] – Set LA [J+1] := LA[J]
4. [Decrease counter] – set J:= J – 1
   [End of step 2 loop]
5. [Insert element] – set LA[K]:= ITEM
6. [Reset N] – set N:= N+1
7. Exit

Program to insert at a position on an Array

void insertElement(int array[], int *n, int elem, int pos)
{
    int i;
    for (i = (*n) - 1; i >= pos; i--)
    {
        array[i + 1] = array[i];
    }
    array[pos] = elem;
    (*n)++;
}

Deletion in an array

• Deleting refers to the operation of removing one element to collection A.
• Deleting an element at the “end” of the linear array can be easily done with difficulties.
• If an element at the middle of the array needs to be deleted, then each subsequent elements be moved one location upward to fill up the array.

Algorithm
DELETE (LA, N, K, ITEM)
Here LA is a linear array with N elements and K is a positive integer such that K ≤ N. this
algorithm deletes the Kth element from LA

1. Set ITEM:= LA[K]
2. Repeat for J = K to N – 1
   [Move J + 1 element upward] set LA[J]:= LA[J+1]
   [End of loop]
3. [Reset the number N of elements in LA] set N:= N – 1
4. Exit

Program for Deleting an Array

void deleteElement(int array[], int *n, int pos)
{
    int i;
    for (i = pos; i < (*n) - 1; i++)
    {
        array[i] = array[i + 1];
    }
    (*n)--;
}

Example: Inserting and Deleting

Suppose NAME is an 8-element linear array, and suppose five names are in the array, as in Fig.(a).

Observe that the names are listed alphabetically, and suppose we want to keep the array names alphabetical at all times. Suppose Ford is added to the array. Then Johnson, Smith and Wagner must each be moved downward one location, as in Fig.(b). Next suppose Taylor is added to the array; then Wagner must be moved, as in Fig.(c). Last, suppose Davis is removed from the array. Then the five names Ford, Johnson, Smith, Taylor and Wagner must each be moved upward one location, as in Fig.(d).