Operations on Arrays in Data Structures: Traversal, Insertion, Deletion and Searching

Operations on an Array: While there are many operations that can be implemented and studied, we only need to be familiar with the primary ones at this point. An array supports the following operations:

• Traversal
• Insertion
• Deletion
• Search

Other operations include sorting ascending, sorting descending, etc. Let's follow up on these individually.

Traversal:

Visiting every element of an array once is known as traversing the array.

Why Traversal?
For use cases like:

• Storing all elements – Using scanf
• Printing all elements – Using printf

Updating elements. An array can easily be traversed using a for loop in C.

An Important Note on Arrays:
If we create an array of length 100 using int arr[100]; in C, we do not need to use all the elements. It is possible for a program to use just 60 elements out of these 100. (But we cannot go beyond 100 elements).

Insertion:

An element can be inserted into an array at a specific position. For this operation to succeed, the array must have enough capacity. Suppose we want to add the element 10 at index 2 in the illustrated array; then, the elements after index 1 must shift to their adjacent right to make way for the new element.

When no position is specified, it’s best to insert the element at the end to avoid shifting, and this is when we achieve the best runtime O(1).

Deletion:

An element at a specified position can be deleted, creating a void that needs to be fixed by shifting all the elements to their adjacent left, as illustrated in the figure below.

We can also bring the last element of the array to fill the void if the relative ordering is not important. :)

Quick Quiz: What is the best and the worst runtime for a delete operation?

Searching:

Searching can be done by traversing the array until the element to be found is located, which takes O(n) time. However, there is a better method. As you may remember, both linear and binary search methods were analyzed. The binary search method is applicable only for sorted arrays. Therefore, for sorted arrays, the time taken to search is significantly less than for unsorted arrays, taking O(log n) time.

Sorting:

Sorting means arranging an array in an orderly fashion (either ascending or descending). There are different algorithms available to sort arrays.

So, these were a few primary operators for an abstract data type array. Today, we had their introduction and visualization. We can now move on to coding them in our editors and see how these algorithms work.

We discussed four operations: traversal, insertion, deletion, and searching. As mentioned, traversal is straightforward and can be achieved using a for loop. Our main objective today will be to implement insertion. So, let’s slide our chairs to our coding arena. Attached the code snippet below.

Understanding code snippet 1:

1. We will start by declaring an array arr of length 100 and initialize this array with some 4-5 elements. This will be our used memory.

2. We’ll create a void display function using the method of traversal. Pass this array to the display function by value or by reference, and print the elements. Printing the elements of an array has already been covered in my C playlist. Visit now if you haven’t yet.

3. We’ll now create an integer function indInsertion (integer, just to check if the operation succeeds). Before that, create an integer variable size to store the used size of the array. Pass into this void function the array and its used size, the element to be inserted, the total size, and the index where it is inserted.

indInsertion(arr, size, element, 100, index);

4. In the indInsertion function, write the case of validity. Here, we’ll check if the index is within the range [0,100]. We’ll continue if it's valid; otherwise, return -1.

5. Create a for loop to shift the elements from the index to the last element to their adjacent right. This way, we’ll create a void at the index we want to insert in.

6. Insert the element at the index and return 1 on completion.

#include<stdio.h>
 
 
void display(int arr[], int n){
    // Code for Traversal
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");   
}
 
int indInsertion(int arr[], int size, int element, int capacity, int index){
    // code for Insertion
    if(size>=capacity){
        return -1;
    }
    for (int i = size-1; i >=index; i--)
    {
        arr[i+1] = arr[i];
    }
    arr[index] = element;
    return 1; 
}
 
int main(){
    int arr[100] = {7, 8, 12, 27, 88};
    int size = 5, element = 45, index=1;
    display(arr, size); 
    indInsertion(arr, size, element, 100, index);
    size +=1;
    display(arr, size);
    return 0;
}

Code Snippet 1: Insertion Operation Algorithm

Output of the above program:

7 8 12 27 88 
7 45 8 12 27 88

So, as you can see, element 45 got inserted at index 1, and the rest of the elements from this index to the last shifted to their right. And this is how we do an insertion in an array. We may come across a lot of variations to insert into an array, but we’ll go slow for now.

Quiz: Modify this program to display the array only after a successful insertion, otherwise print Insertion failed.

Deletion

Programming a deletion differs very slightly from programming an insertion. In insertion, we had to shift elements to their adjacent right to create a void at the desired place to insert a new element, but in deletion, we’ll shift the elements to their adjacent left to fill the void created after deleting an element at some index.

Let us now code this out or rather transform the code we constructed to insert the element. I have attached the snippet below.

Understanding code snippet 1:

1. One thing which will remain as it is, is the display function.

2. We have to make minimal changes in the insertion function to make it a deletion function. Rename it indDeletion. The index and the array, and its size will be our only parameters this time.

3. Replace the right shift with the left shift. Just assign array[i] the value present in array[i+1].

4. And we are done deleting the element at some specified index.

#include <stdio.h>
 
void display(int arr[], int n)
{
    // Code for Traversal
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
 
void indDeletion(int arr[], int size, int index)
{
    // code for Deletion
    for (int i = index; i < size-1; i++)
    {
        arr[i] = arr[i + 1];
    }  
}
 
int main()
{
    int arr[100] = {7, 8, 12, 27, 88};
    int size = 5, element = 45, index = 0;
    display(arr, size);
    indDeletion(arr, size, index);
    size -= 1;
    display(arr, size);
    return 0;
}

Code Snippet 1: Deletion in an array:

We can now check if the program actually works for deleting the element at some index. We’ll create an array with 5 elements and display it before and after deleting an element at index 0.

Refer to the output below:

7 8 12 27 88 
8 12 27 88
PS D:\MyData>

Figure 1: Output of the above program

The code works fine. The element at index 0 got deleted, and the rest of the elements shifted left to fill the void created after deletion. This was all about the deletion. Only a subtle change of code helped transform insertion into deletion.