Array in Data Structure

In this section of the tutorial, we will discuss the Array and its implementation, the time complexity of Array operations on Data Structure, and the passing of Array to Function.

Now let’s move further to the introduction of the collection of similar data items in a Data Structure, i.e. Array.

What are Arrays in Data Structure?

In an Array, the list of data items is maintained in a sequential order in accordance with the order structure of the elements in the array, i.e. indexes. Searching an Array for a desired element is efficient but the insertion and deletion of elements of an Array is a complex operation to perform.

This is why Arrays are used, especially when the list of data items modifies frequently. As for the non-linear Array, the implementation of such an Array can be excessively large, especially when there are several successors of each of the elements.

Now we will go through the use of Array in Data Structure and its properties used in the implementation of Data Structure.

Why do we need Array in Data Structure?

While solving a problem, we may encounter a situation where we need to perform operations on a large amount of data of a similar type. And it becomes an exhausting task to assign a large number of variables to store an individual data item. So here comes the need of using Array in Data Structure operations.

An array is a fixed-sized, structured, and sequential collection of elements of the same kind of data type that share a common name. Since it has a structured form, it can be used in representing values that have a structure of some sort.

  • Arrays are one of many derived data types called data structures including others like stacks, queues, linked lists, trees, etc.
  • Sometimes we write a program where we need to handle large volumes of data in terms of reading, processing, and printing.
  • So to process such a large amount of data, we need a powerful derived data type that would facilitate efficient storing, accessing, and manipulation of data items. Hence, we use Arrays to carry out such big tasks.

We can take an example to demonstrate the number of variables declared each time to store an individual data item.

#include<stdio.h>
int main()
{
  int Marks1,Marks2,Marks3,Marks4,Marks5;
  int Total;
  printf("Enter your marks in the following subjects");
  printf("\nScience: ");
  scanf("%d",&Marks1);
  printf("\nMaths: ");
  scanf("%d",&Marks2);
  printf("\nEnglish: ");
  scanf("%d",&Marks3);
  printf("\nHindi: ");
  scanf("%d",&Marks4);
  printf("\nComputer Applications: ");
  scanf("%d",&Marks5);
  Total=Marks1+Marks2+Marks3+Marks4+Marks5;
  printf("__________________________");
  printf("Total Marks = %d",Total);
  return 0;
}
  • In the above program, we assigned five variables, i.e. Marks1, Marks2, Marks3, Marks4, and Marks5 to store each individual value entered by the user.
  • This increases memory consumption of the computer and the efficiency of the program.
  • So, we use Array to store similar kinds of data items in a single variable in accordance with the index value.

We can take an example to demonstrate the use of Array in a program.

#include<stdio.h>
int main()
{
  int Marks[5];
  int Total;
  printf("Enter your marks in the following subjects");
  printf("\nScience: ");
  scanf("%d",&Marks[0]);
  printf("\nMaths: ");
  scanf("%d",&Marks[1]);
  printf("\nEnglish: ");
  scanf("%d",&Marks[2]);
  printf("\nHindi: ");
  scanf("%d",&Marks[3]);
  printf("\nComputer Applications: ");
  scanf("%d",&Marks[4]);
  Total=Marks[0]+Marks[1]+Marks[2]+Marks[3]+Marks[4];
  printf("__________________________");
  printf("Total Marks = %d",Total);
  return 0;
}
  • In the above program, the Array Marks[5] is declared that can hold data items equal to its size, i.e. 5.
  • So, the need of using Array is that we can get past the hard work required to declare and access data items using different variables.
  • This makes the program efficient and saves a lot of computer’s memory.

How to access Array elements?

The data stored inside the elements of an array can be accessed using the index values assigned to each element.

For example, if we declared an array such as, int Marks[5] = {70,75,80,90,95};
Then we can access any particular element using its index number. Like if we want to access the 3rd element of the given array,
we can use Marks[2].

In general, for accessing an nth element we can use array_name(n-1)th index number.

We will understand how we can access array elements with the help of an example given below.

#include<stdio.h>
int main()
{
  int Marks[5];
  int Total;
  printf("Enter your marks in the following subjects");
  printf("\nScience: ");
  scanf("%d",&Marks[0]);
  printf("\nMaths: ");
  scanf("%d",&Marks[1]);
  printf("\nEnglish: ");
  scanf("%d",&Marks[2]);
  printf("\nHindi: ");
  scanf("%d",&Marks[3]);
  printf("\nComputer Applications: ");
  scanf("%d",&Marks[4]);
  Total=Marks[0]+Marks[1]+Marks[2]+Marks[3]+Marks[4];
  printf("__________________________");
  printf("Total Marks = %d",Total);
  return 0;
}

Here, in line 8 of the above code, &Marks[0] is used to access the address of the element and at index value 0. And so that, the value input from the user can be stored in that particular element.

Array implementation in Data Structure

Arrays can be used in several operations where a large amount of data are to be handled in a program.

Arrays are used frequently in searching and sorting operation where a large pool of data values are taken by the program to sort these data values in a particular order or find a particular value among many data values.

Few basic sorting techniques used are:

  • Bubble sort
  • Selection sort
  • Insertion sort

Two most commonly used searching techniques are:

  • Sequential search
  • Binary search

Time and Space Complexity of Array operations

Below is a table that lists the space and time complexity of Array implementation for various Sorting and Searching operations.

Operations
Average Case
Worst Case
Space Complexity

Insertion

 O(n) O(n) O(n)
Access O(1) O(1)

O(n)

Search

 O(n) O(n) O(n)
Deletion O(n) O(n)

O(n)

Array and Function in Data Structure

Arrays can be passed to Functions in the same way as we pass normal variables to a function.

To pass an Array to a called Function, we just have to follow the process given below:

  • Listing the name of the Array without its index values.
  • Specifying the size of the arrays as Function arguments, but not necessary.

The general form for passing Array to Function could be:

datatype function-name(datatype array-name[])

Below is an example for us to understand how we can pass an Array to a Function.

Example: Passing a single element of an Array to called Function.

Sample Code:

#include<stdio.h>
void Array1(int a);
int main()
{
    int a[] = {10,20,30};
    Array1(a[1]);
    return 0;
}
void Array1(int n)
{
    printf("%d\n",n);
}

Output:

20

Example: Passing a complete Array to called Function.

Sample Code:

#include<stdio.h>
int FindVal(int a[], int n);
int main()
{
    int FindVal(int a[], int n);
    int a[4] = {10,20,30,40};
    printf("%d\n",FindVal(a,4));
}
int FindVal(int a[], int n)
{
    int i;
    int max;
    max = a[0];
    for ( i = 1; i < n; i++)
    {
        if(max < a[i])
        max = a[i];
    }
    return(max);
}

Output:

40

Important points to note:

  • If a called Function changes the values of the elements of an Array, then these changes will modify the values present in the Original Array too.
  • This happens because when an entire Array is passed as an argument to the called Functions, the values are not copied, instead, the address of the Array elements is passed into the formal parameter.
  • So any changes made in the Arrays will modify the values of the Original Array present in the calling Function too.
  • However, this case is not applied if an individual element is passed on as an argument to the called Function.
  • Also, we cannot pass the whole Array by value to the called Function.
  • Passing addresses to the function is referred to as pass by address or pass by pointers.

Rules to pass an array to functions

However, there is a set of rules that must be kept in mind before we pass an Array as arguments to the called Function.

  • Only the name of the Array must be passed to the called Functions.
  • In the Function definition, the formal parameter must be an Array type, where specifying the size of the Array is not necessary.
  • The Function prototype must show the Array as an argument.

In the next section of the tutorial, we will discuss the use of 2D Array in Data Structure and we will learn the properties of 2D Array, important operations on Array such as mapping a 2D Array into a 1D Array and finding the address of a random 2D Array element which will be used thoroughly later in this Data Structure tutorial.