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

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.

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

public class JavaExample{
   public static void main(String args[]) {
 //array declaration
 int arr[]; 
  
 //allocating memory to array
 arr = new int[10];
    
 //Assigning elements
 arr[1] = 100;
 arr[5] = 98;
 arr[3] = 11;
  
 //Accessing array elements
 for(int i=0; i<10 ; i++) {
  System.out.println(arr[i]);
 }
   }
}

Time complexity of Array

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

Operation	Average Case	Worst Case
Read	O(1)	O(1)
Insert	O(n)	O(n)
Delete	O(n)	O(n)
Search	O(n)	O(n)