Arrays in the Data Structure

In My Second day of DS & Algo Internship at Internity Foundation, I have learned about the Importance of Arrays in Data Structure.

An array is a collection of homogeneous (same type) data items stored in contiguous memory locations. For example if an array is of type “int”, it can only store integer elements and cannot allow the elements of other types such as double, float, char etc.

Array Memory representation

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

Why we need an array?

Array is particularly useful when we are dealing with lot of variables of the same type. For example, lets say I need to store the marks in math subject of 100 students. To solve this particular problem, either I have to create the 100 variables of int type or create an array of int type with the size 100.

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 array is simple and easy, all 100 values can be stored in the same array at different indexes (0 to 99).

Accessing Array elements

In this example we have an array arr of type “int”. The size of the array is 10 which means it can hold 10 integer values. arr[0] would be first element, arr[1] second and so on. Here we are assigning values to only few elements of the array. After this program, I have shared the output of this program, which shows that the default value of the elements of an int array is 0. The elements that are not assigned any value shows their value as 0 (default value).

int main(){
   int arr[] = {2,4,6,8,10,12};
   int length_of_Array = sizeof(arr)/sizeof(arr[0]);
   //printing size of array
   cout<<length_of_Array<<endl;
   //Accessing the array elements
   cout<<arr[1];  //4
   cout<<arr[4];  //10
}

Time complexity of Array

Lets take a look at the time complexity of various operations on arrays.

Advantages and disadvantages of Arrays

Advantages

1. Reading an array element is simple and efficient. As shown in the above table, the read time of array is O(1) in both best and worst cases. This is because any element can be instantly read using indexes (base address calculation 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 array.

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

1. While using array, we must need to 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 array, it would make the task difficult.

2. The size of the array is fixed so if at 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.

2D Array

2D array is known as array of arrays and are used to represent matrix of elements

An array of arrays is known as 2D array. The two dimensional (2D) array in C programming is also known as matrix. A matrix can be represented as a table of rows and columns. Before we discuss more about two Dimensional array lets have a look at the following C program.

Simple Two dimensional(2D) Array Example

For now don’t worry how to initialize a two dimensional array, we will discuss that part later. This program demonstrates how to store the elements entered by user in a 2d array and how to display the elements of a two dimensional array.

#include<stdio.h>
int main(){
   /* 2D array declaration*/
   int disp[2][3];
   /*Counter variables for the loop*/
   int i, j;
   for(i=0; i<2; i++) {
      for(j=0;j<3;j++) {
         printf("Enter value for disp[%d][%d]:", i, j);
         scanf("%d", &disp[i][j]);
      }
   }
   //Displaying array elements
   printf("Two Dimensional array elements:\n");
   for(i=0; i<2; i++) {
      for(j=0;j<3;j++) {
         printf("%d ", disp[i][j]);
         if(j==2){
            printf("\n");
         }
      }
   }
   return 0;
}

Output:

Enter value for disp[0][0]:1
Enter value for disp[0][1]:2
Enter value for disp[0][2]:3
Enter value for disp[1][0]:4
Enter value for disp[1][1]:5
Enter value for disp[1][2]:6
Two Dimensional array elements:
1 2 3 
4 5 6