Arrays

The start to your coding journey!

An array is a collection of homogeneous data items of the same type. Data items are stored in contiguous memory locations. For example if an array is of type “char”, it can only store character elements and cannot allow the elements of other types such as double, float, int etc. Following are some useful terms to understand the concept of Array better:

1. Element − Each data item stored in an array is known as an element.
2. Index − Each location of an element in an array has a numerical index, which is used to identify the element.

Array Memory representation:

The following diagram represents an integer array that has 11 data elements. The array starts with an index 0, so the array has indexes from 0 to 10 having a total of 11 data items .

There is a difference of 4 among the addresses of neighbours because integer holds 4 bytes of data. Source

Why do we need an array?

Array is used when we have to store a lot of variables of the same data type. For example, let’s say I need to store the percentages of 80 students. To solve this particular problem, either I have to create the 80 variables of float type or create an array of float type with the size 80.

Obviously the second option is best, because keeping track of all the 100 different variables is a tedious task. On the other hand, dealing with arrays is simple and easy, all 100 values can be stored in the same array at different indexes (0 to 99).

How to declare & initialise an array in C?

int num[35]; /* An integer array of 35 elements */
char ch[10]; /* An array of characters for 10 elements */
/*Similarly an array can be of any data type such as double, float, short etc.*/

In this example, we have just declared an array and not initialised it. An uninitialised has garbage values as its elements. We can initialise the array during declaration like this:

int arr[5] = {1,2,3,4,5};
int arr[] = {1,2,3,4,5};
//Both have the same effect

How to access element of an array in C?

You can use array subscript (or index) to access any element stored in the array. Subscript always starts with 0, which means A[0] represents the first element in the array A.

In general A[n-1] can be used to access the nth element of an array. where n is any integer number. For example:

int mydata[20];
mydata[0] /* first element of array mydata*/
mydata[19] /* last (20th) element of array mydata*/

Basic operations on an array include:

1. Traversal
2. Insertion
3. Deletion
4. Search
5. Sorting the elements (in ascending and descending order)

1. Traversing the array:

Traversing an array includes visiting each element in the array sequentially. For example if we want to display all the elements present in the array, we would use a for loop in C:

#include <stdio.h>

int main()
{
    int a[] = {5,4,3,2,1};
    for(int i=0; i<5; i++){
        printf("%d ",a[i]);
    }
}
//Output would be: 5 4 3 2 1

2. Insertion:

1. Input data into the array sequentially:

When we initialise all the elements of an array, by using a for loop. The values can be taken from the user, using a scanf function.

int num[4];
int x;
for (x=0; x<4;x++)
{
//The value for each element will be accepted from the user
    printf("Enter number %d \n", (x+1));
    scanf("%d", &num[x]);
}

2. Input data into the array at a specific position:

We can insert an element in an array at a specific position. We can achieve this only when the array has enough capacity. If we want to add an element at a specified index, then the elements after that specified index must get shifted to their adjacent right to make way for a new element.

#include <stdio.h>

int main()
{
    int array[100];
    int position, c, n, value;
    printf("Enter number of elements in array\n");
    scanf("%d", &n);
    
    printf("Enter %d elements\n",n);
    
    for(c = 0; c < n; c++){
        scanf("%d",&array[c]);
    }
    
    printf("Enter the location where element is to be inserted\n");
    scanf("%d",&position);
    
    printf("Enter the value to be inserted\n");
    scanf("%d",&value);
    
    for(c = n-1; c>=position-1; c--){
        //Shifting all the elements rightward to get position space free.
        array[c+1] = array[c];
    }
    
    //Assigning the value to its index
    array[position - 1] = value;
    
    printf("Resultant array is: \n");
    for(c=0; c<=n; c++){
        printf("%d ",array[c]);
    }
    
    return 0;
}

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).

3. Deletion:

We can delete an element at a specified position in an array but this will create a void in the given array . We can fix this by shifting all the elements to the right of the deleted element to their adjacent left positions .

#include <stdio.h>

int main()
{
    int array[100];
    int position, c, n;
    printf("Enter number of elements in array\n");
    scanf("%d", &n);
    
    printf("Enter %d elements\n",n);
    
    for(c = 0; c < n; c++){
        scanf("%d",&array[c]);
    }
    
    printf("Enter the location from where element is to be deleted: \n");
    scanf("%d",&position);
    
    if(position >= n+1){
        printf("Deletion is not possible.\n");
    }
    else{
        for(c = position - 1; c < n - 1; c++){
            //Shifting the elements to the left
            array[c] = array[c+1];
        }
        
        printf("Resultant array is: \n");
        
        for(c=0; c < n - 1; c++){
            printf("%d ",array[c]);
        }
    }
    return 0;
}

4. Searching:

We can perform searching for an element in an array by traversing the array until the element is found. The time complexity of searching operation is — O(n). We can use Binary Search to search for an element in a Sorted Array. We have a separate bulletin coming up just for this!

Let us see how to solve a problem using arrays:

Q. Use arrays in C to find out average of 4 numbers:

#include <stdio.h>
int main()
{
    int avg = 0;
    int sum =0;
    int x=0;

    /* Array- declaration – length 4*/
    int num[4];

    /* We are using a for loop to traverse through the array
     * while storing the entered values in the array
     */
    for (x=0; x<4;x++)
    {
        printf("Enter number %d \n", (x+1));
        scanf("%d", &num[x]);
    }
    for (x=0; x<4;x++)
    {
        sum = sum+num[x];
    }

    avg = sum/4;
    printf("Average of entered number is: %d", avg);
    return 0;
}
//Output: 
/*
Enter number 1 
10
Enter number 2 
10
Enter number 3 
20
Enter number 4 
40
Average of entered number is: 20
*/

Time Complexity in Arrays:

Time Complexity for performing various operations on an array.

Advantages of using an array:

1. Reading an array element is simple and efficient. As shown in the above table, the read time of the array is O(1) in both best and worst cases. This is because we can access any element in an array by directly specifying the index (base address calculation is done behind the scene) without traversing the whole array.

2. Array is a foundation of other data structures. For example other data structures such as LinkedList, Stack, Queue etc. are implemented using arrays.

3. All the elements of an array can be accessed using a single name (array name) along with the index, which is readable, user-friendly and efficient rather than storing those elements in different-2 variables.

Disadvantages of an array:

1. While using arrays, we must make the decision of the size of the array in the beginning, so if we are not aware how many elements we are going to store in the array, it is difficult to use.

For eg. If we want to register students for a dance competition in our college and we wish to store all student’s names in an array but we are unaware of how many people will be registering for the competition, in such a case , it is difficult to declare the size of an array in the beginning itself . This is a drawback of an array .

2. The size of the array is fixed so at a later point, if we need to store more elements in it then it can’t be done. On the other hand, if we store less number of elements than the declared size, the remaining allocated memory is wasted.

Upcoming topics for the blogs:

For queries regarding the content, please drop a mail to loop@cumminscollege.in Links for in-depth studying and practice problems are sent via mail to students of the college on the date of publishing of the blog by Loop Club. The content is a part of DSA Bulletins started by Team Loop, to provide thorough knowledge and facilitate the learning of new topics of DSA. We are a group of students who are passionate about CP and DSA and want to create awareness and help students in the above topics.