Arrays In Depth

Arrays are one of the most basic data structures used today.

Arrays can be defined as a data structure that holds the same group of elements, which are stored at contiguous memory locations.

They are stored in contiguous memory locations to guarantee randomized access for a particular element.

Arrays are best for fast lookup,i.e if you know the base address of the array, we can access any element in the array at constant time.

Types of Arrays:

  • One Dimensional Array ( int A[10] =new int[10] )
  • Two Dimensional Array (int A[10][10]=new int[10][10] )
  • Multi Dimensional Array (int A[10][10][10]=new int[10][10][10] )

Main Memory or any storage is just a contiguous list of addresses, hence in order to write better programs, one needs to design & implement a data structure in such a way that it optimizes performance.

Addresses in memory start from 0000 and can go up to the size of memory that is available for use.

How are Arrays Stored In Memory

Suppose If we declare array “A” in Java & assign memory to it (refer “new” operator in java):

int A[]=new int[9];

“A” would occupy 9 contiguous memory locations in the memory to store integers.

A [ 0 – 8 ] would be the index range for array.

Hence, In Order to access the first element & last element

We can write:

System.out.println("FIRST: "+A[0]+"LAST : "+A[8]);

Array Terminologies:

Base Address: It represents the starting address of the array.


Index: It represents the location of an array element.

Size: It represents the number of elements array can hold.

One Dimensional array can be stored easily in the computer’s main memory, as they occupy contiguous memory locations.

Two Dimensional Arrays are organized in memory by two types :

  • Row Major Order (Row By Row)
  • Column Major Order (Column By Column)

In the Row Major Order , the array is organized in the memory row by row.

If we write:-

int A[][]=new int[4][2]

then, element 10 would be at A[0][0] and 60 would be at A[2][1] & so on.

while,In main memory, it would be stored as contiguous blocks.

Access Particular Element In Row Major Order:

  • Based on 0 indexing
  • Based on 1 indexing

0 Based Indexing:

Suppose we want to access a particular element A[2][0] in a row major order scheme,

then, We have to skip 2 rows & no columns , to get the element A[2][0].

hence,In Array[ M][ N ] , To find the address of an element A[i][j] ,we can write as:

A[i][j]=[ ( i * N ) + j ] * SIZE + Base Address of array.

1 Based Indexing:

In case of 1 based indexing, the find address of element A[2][1], we have to skip 1 row & no columns ,hence we can write as:

(Note: SIZE represents size of data type array is storing)

A[i][j]=[ ( ( i - 1 )* N ) + ( j - 1 ) ] * SIZE +Base Address of array.

In the column major order,the array is organized in the memory column by column.

In Memory,it would be still stored in form of contiguous blocks.

Access Particular Element In Column Major Order:

  • 0 Based Indexing
  • 1 Based Indexing

(Note: SIZE represents size of data type array is storing)

0 Based Indexing

In zero-based indexing,to address of a particular element A[i][j] in A[M][N], we can write as:

A[i][j]=[ ( ( j * M ) + i ) ] * SIZE + Base address of array.

1 Based Indexing

In one-based indexing, to address of a particular element A[i][j] in A[M][N], we can write as

A[i][j]=[ ( ( j - 1 ) * M +( i - 1 ) ) ] * SIZE + Base address of array.

Array Operations

  • Traversing
  • Insertion
  • Deletion
  • Searching
  • Sorting
  • Merging

Traversing In Array

Traversing in the array refers to visiting every element in the array.

void traverse(int x[],int n){
 for(int i=0;i<n;i++){
  printf("%d",x[i]);
 }
}

Insertion in Array

Insertion in array can be done by inserting an element at specific position ,provided the array is not full.

Insertion At Specific Position
void insert(int x[],int n,int loc,int ele){
 int i;
 for(i=n-1;i>loc;i--){
  x[i]=x[i-1];
 }
 x[loc]=ele;
}

Deletion In Array

Deletion is basically carried out by shifting the elements , with respect to the location provided.

Deletion In Array
void deletion(int x[],int n,int loc){
 int i;
 for(i=loc;i<n;i++){
  x[i]=x[i+1];
 }
 n=n-1;
}

Searching In Array

Searching returns the index of element if found. it will return -1 if specified element is not found.

int search(int x[],int n,int ele){
 for(int i=0;i<n;i++){
   if(x[i]==ele){
     return i;
   }
 }
 return -1;
}

Sorting in Array

Sorting basically sorts the array of elements in either ascending or descending order.

void sort(int x[],int n){
 for(int i=0;i<n;i++){
  for(int j=i;j<n-i-1;j++){
   if(x[j] > x[j+1]){
     int temp=x[j];
     x[j]=x[j+1];
     x[j+1]=temp;
    }
  }
 }
}

Merging Arrays

Merging operation concatenates 2 different arrays into one array.

Merging Arrays
void merge(int x[],int m,int y[],int n,int z[]){
 int i,j;
 j=0;
 for(i=0;i<m;i++){
  z[j]=x[j]'
  j=j+1;
 }
 for(i=0; i < n ;i++){
  z[j]=y[i];
  j=j+1;
 }
}

Array Operations Time Complexity

Below table summarizes the time complexities of performing operation on arrays.

Array Operation Time Complexity

Array Utilities

In Java, we have methods from java.util.Arrays class to perform any operation on the array.

Some of these methods are:-

binarySearch(arr[],from,end,key) – binarySearch function returns index of element found in array after binary search,if not found returns -1.

equals(arr[],arr[]) – compares 2 arrays , returns true if they are equal,else false.

sort(arr[]) – sorts the array, you can even specify the start & end index.

(Note: Refer here for more details)

In the next article, we will look into some array coding questions for interviews.

Any Suggestions to improve this article are always welcomed!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Create your website at WordPress.com
Get started
%d bloggers like this: