Data Structure Array

Array

A collection of similar types of data items stored at contiguous memory locations is called an array. Being a derived data type in C programming language, an array can store the primitive type of data such as int, char, double, float, etc. The data element of an array can be randomly accessed by using its index number and is often called as the simplest data structure.

Example:

To store the seven digits of a number separately, we don’t need to define different variables for the different digits. By defining an array, we can store the different digits at the contiguous memory locations. The array digits[7] define the seven digits of the number where each number digit is located at a particular subscript in the array i.e. digits[0] denotes the digit in the first place, digits[1] denote the digit in 2nd place, and so on.

Properties of the Array:

In an array, each element is of the same data type.
In an array, each element carries the same size. For example, int = 4 bytes.
In an array, the elements are stored at contiguous memory locations. The first element is thus stored at the smallest memory location.
In an array, the elements can be randomly accessed. The address of each element of the array can be calculated with the given base address and the size of the data element.

Declaring an array: In C language:

int a[20]; 
char a[20]; 
float a[10]

Need of using an Array:

To store a large number of data of similar type, in computer programming, we need to define a large number of variables. Remembering the name of all the variables while writing the programs is not an easy task. It is undoubtedly better to define an array and store all the elements into it, instead of naming all the variables with a different name.

Example without array:

#include <stdio.h>  
void main ()  
{  
    int years_1 = 6, years_2 = 7, years_3 = 8, years_4 = 6, years_5 = 10;   
    int sum = (years_1 + years_2 + years_3 + years_4 + years_5)  ;  
    float avg = sum/5; 
    printf("%f", avg);   
}

Output

7.400000

Example with an array:

#include <stdio.h>  
void main ()  
{  
    int years[5] = {6,7,8,6,10};  
    int i;    
    float sum, avg;  
    for (i=0; i<5; i++)   
    {  
        sum = sum + years[i];  
 
    }    
    avg = sum/5;
    printf("%f", avg);   
}

Output

7.400000

Explanation:

In the above examples, we are trying to define the importance of using arrays in writing code for a particular problem. Here, we have stored the years of experience of the employees of a company and intend to calculate the average of all the years of experience of the employees. By creating the two above programs, one without using an array and the other using an array to store the years of experience of the employees, we are trying to illustrate the importance of arrays.

The complexity of Array operations:

In the below table, we are listing the time and space complexity of various array operations.

Time Complexity:

Algorithm	Average Case	Worst Case
Access	O(1)	O(1)
Search	O(n)	O(n)
Insertion	O(n)	O(n)
Deletion	O(n)	O(n)

Space Complexity:

The space complexity for the worst case in an array is O(n).

Array’s Advantages:

A single name for the group of variables of the same type simply means that it is easy to remember the name of all the elements of an array.
We just need to increment the base address of the array in order to visit each element one by one to traverse an array.
By using the index, we can directly access any element in an array.

Memory Allocation of the array:

All the data elements of an array are stored at contiguous locations in the main memory and each element of the array is represented by proper indexing. The base address or the address of the first element in the main memory is represented by the name of the array.

There are three ways to define the indexing of the array. These are:

0 (zero-based indexing): In zero-based indexing, the first element of the array is a[0]. If the size of an array is n then the maximum index number, an element can have is n-1.

1 (one-based indexing): In the one-based indexing, the first element of the array is a[1]. If the size of an array is n then the maximum index number, an element can have is n.

n (n – based indexing): In the n-based indexing, the first element of the array can reside at any random index number.

Accessing Elements of an array:

The below information is required to access any random element of an array.

Base Address of the array.
Size of an element in bytes.
The type of indexing that array follows.

To calculate the address of an element of a 1D array:

Byte address of element A[i] = base address + size * ( i - first index)

Example :

In an array, A[-10 ..... +2 ], Base address (BA) = 1000, size of an element = 2 bytes,

find the location of A[-2].

L(A[-2]) = 1000 + [(-2) - (-10)] x 2

= 1000 + 16

= 1016

Passing array to the function:

By using the base address, we can traverse all the elements of an array. The base address or the address of the first element is represented by the name of the array. An array can also be passed to a function.

Example:

#include <stdio.h>  
int addition(int[]);  
void main ()  
{  
    int a[5] = {5,15,20,25,35};  
    int add = addition(a);   
    printf("%d",add);   
}   
 
int addition (int a[])   
{  
    int add=0,i;   
    for (i = 0; i<5; i++)   
    {  
        add = add + a[i];   
    }   
    return add;   
}

Output

Explanation:

In the above example, we are defining a function “addition”. This function accepts an array as an argument to calculate the sum of all the elements of the array and return it.