Array - It is a linear, static, type safe user defined data structure. Since array elements are stored in the RAM memory in contiguous manner its elements are accessed through its index.
Time complexity to access an array element is O(1) as address of any element is calculated directly using index and base address of given array. Using this address a given element is accessed.
Array Access method- If arr is an array, then array element at index i is represented as arr[i]
Suppose size of one array element is ELE_SIZE byte and base address of array is BASE_ADR. Then address of an array element at given index is calculated as:
Address of array element=BASE_ADR+index*ELE_SIZE
Characteristics of Array:
a. Linear - It means here data are stored sequentially in the RAM memory and there is always a unique predecessor and successor. Below is the example:
b. Static - Array is static data structure. While creating the array we have to specify its size. Once array is created its size can't be modified.
c. Type Safe- Type safe is a generic concept which means while creating the object its type information must be supplied as well, to maintain its type information by complier to avoid any problem of data type mismatch at run time. Below is the syntax of creating array in JAVA of size SIZE with data.
int [] arr=new int[SIZE]
The above syntax indicates that an array of integers of size "SIZE" with name arr is created in the memory.
Operations on Array:
Below is an example of array data structure written in JAVA language:
class HelloWorld {
public static void main(String[] args) {
int SIZE=10;
int []arr;//Array declaration
arr=new int[SIZE];//Array creation of size 10
arr[0]=1;//Array element initialization
arr[1]=2;
arr[3]=10;
arr[5]=11;
for(int i=0;i<10;i++)
{
System.out.println("Array element at index-"+i+" is:"+arr[i]); //Accessing array element
}
}
}
In the above example an array of size 10 is created. Some elements are initialized and accessed inside for loop. For better understanding comments are provided in the code which are self explanatory.
Operations on Array:
Addition/Modification/Retrieval- Addition, modification or retrieval of an element in an array is performed using index. As mentioned above using the index, exact address of the given index element will be calculated. Due to the direct address calculation Addition, Modification and Retrieval of a element from an array based on the index takes time complexity O(1). Below is JAVA code snippet to illustrate this.
int SIZE=10;
int []arr;//Array declaration
arr=new int[SIZE];//Array creation of size 10
arr[0]=1;//Array element initialization/Addition
arr[1]=2;
arr[0]=5;//Array element modification
int val=arr[1];//Array element retrieval
Deletion- Since array is static, no physical addition or deletion of elements are allowed here. To delete an element from array below two techniques can be applied.
a. Using new array - Here new array is created and remaining elements which are supposed to be part of final array(excluding the element which needs to be deleted) are copied to new array. This operation is very costly where an extra array is created and elements are copied one by one from one array to another array. Here time complexity and space complexity both are O(n). Below code snippet depicts the same:
class HelloWorld {
public static void main(String[] args) {
int SIZE=5;
int []arr;//Array declaration
arr=new int[SIZE];//Array creation of size 10
arr[0]=1;//Array element initialization/Addition
arr[1]=2;
arr[2]=3;
arr[3]=4;
arr[4]=5;
System.out.println("============Original array============");
for(int i=0;i<arr.length;i++)
{
System.out.print(arr[i]+"\t");
}
int[] arr_mod=new int[SIZE-1];
int item_to_delete_index=2;//We are going to delete item present at index 2
int mod_index=0;
for(int i=0;i<arr.length;i++)
{
if(i!=item_to_delete_index)
{
arr_mod[mod_index]=arr[i];
mod_index++;
}
}
System.out.println("============Modified array============");
for(int i=0;i<arr_mod.length;i++)
{
System.out.print(arr_mod[i]+"\t");
}
}
}
Below picture shows above mentioned delete method:
b. Using shifting of elements - Here a variable is used to track last valid element of the array. Any element index greater than this variable value is treated as invalid. If and element at index i needs to be deleted in an array where last valid index is v then
if i==v then just v=v-1
else shift all elements from i+1 to v of array to one step back in the position and then at last update v=v-1. Below code snippet depicts the same.
class HelloWorld {
public static void main(String[] args) {
int SIZE=5;
int []arr;//Array declaration
arr=new int[SIZE];//Array creation of size 10
int valid_index=-1;
arr[0]=1;//Array element initialization/Addition
valid_index++;
arr[1]=2;
valid_index++;
arr[2]=3;
valid_index++;
arr[3]=4;
valid_index++;
arr[4]=5;
valid_index++;
System.out.println("============Original array============");
for(int i=0;i<=valid_index;i++)
{
System.out.print(arr[i]+"\t");
}
int item_to_delete_index=2;//We are going to delete item present at index 2
for(int i=item_to_delete_index;i<valid_index;i++)
{
arr[i]=arr[i+1];//Shifting of elements
}
valid_index--;
System.out.println("============Modified array============");
for(int i=0;i<=valid_index;i++)
{
System.out.print(arr[i]+"\t");
}
}
}
Below picture shows above mentioned delete method:
This is better approach to delete an element from array rather than creating new array. Here time complexity of operation is O(n) and space complexity is O(1).