Array

1. Theory
2. Problem solving

Introduction

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together.

Array’s size –Fixed

In C language array has a fixed size meaning once the size is given to it, it cannot be changed i.e. you can’t shrink it neither can you expand it. The reason was that for expanding if we change the size we can’t be sure ( it’s not possible every time) that we get the next memory location to us as free. The shrinking will not work because the array, when declared, gets memory statically, and thus compiler is the only one to destroy it.

Arrays in Java

Memory allocation: In Java all arrays are dynamically allocated. (but having fixed size,the size can’t be changed once allotted whether statically or dynamically i.e more discussed below)

Array can contain primitives (int, char, etc.) as well as object (or non-primitive) references of a class depending on the definition of the array. In case of primitive data types, the actual values are stored in contiguous memory locations. In case of objects of a class, the actual objects are stored in heap segment.

1-D Array in java

//The general form of a one-dimensional array declaration is
type var-name[];
OR
type[] var-name;

Example: 
// both are valid declarations
int intArray[]; 
or int[] intArray; 

Although the first declaration above establishes the fact that intArray is an array variable, no actual array exists. It merely tells the compiler that this variable (intArray) will hold an array of the integer type. To link intArray with an actual, physical array of integers, you must allocate one using new and assign it to intArray.

Instantiating an Array in Java When an array is declared, only a reference of array is created. To actually create or give memory to array, you create an array like this:

var-name = new type [size];

To use new to allocate an array, you must specify the type and number of elements to allocate.

Note About Array

• The elements in the array allocated by new will automatically be initialized to zero (for numeric types), false (for boolean), or null (for reference types).Refer Default array values in Java
• Obtaining an array is a two-step process. First, you must declare a variable of the desired array type. Second, you must allocate the memory that will hold the array, using new, and assign it to the array variable. Thus, in Java all arrays are dynamically allocated. (But once allocated it’s of fixed size can’t be changed at runtime as in case of linked-list)

Array Literal

In a situation, where the size of the array and variables of array are already known, array literals can be used.

int[] intArray = new int[]{ 1,2,3,4,5,6,7,8,9,10 }; 
 // Declaring array literal

Multidimensional Arrays

Multidimensional arrays are arrays of arrays with each element of the array holding the reference of other array. These are also known as Jagged Arrays.

int[][] intArray = new int[10][20]; //a 2D array or matrix
int[][][] intArray = new int[10][20][10]; //a 3D array

Accessing Jagged array

class multiDimensional
{
	public static void main(String args[])
	{
		// declaring and initializing 2D array
		int arr[][] = { {2,7,9},{3,6,1},{7,4,2} };

		// printing 2D array
		for (int i=0; i< 3 ; i++)
		{
			for (int j=0; j < 3 ; j++)
				System.out.print(arr[i][j] + " ");

			System.out.println();
		}
	}
}

//2D Arrays Operation
	int arr[][] = { {2,7,9},{3,6,1},{7,4,2} };

//number of rows
arr.length;

//number of columns in each-row
arr[i].length;

Array Members

• The public final field length, which contains the number of components of the array. length may be positive or zero.
• All the members inherited from class Object; the only method of Object that is not inherited is its clone method.
• The public method clone(), which overrides clone method in class Object and throws no checked exceptions. (as opposed to Object’s clone method throws CloneNotSupportedException )

Array can be copied to another array using the following ways in java:

• Using variable assignment. This method has side effects as changes to the element of an array reflects on both the places. To prevent this side effect following are the better ways to copy the array elements.
• Create a new array of the same length and copy each element.
• Use the clone method of the array. Clone methods create a new array of the same size.
• Use System.arraycopy() method. arraycopy can be used to copy a subset of an array.
• Use Arrays.copyOf() to copy first few elements of array or full copy.
• Use Arrays.copyOfRange() to copy specified range of a specific array to new array.

Cloning of arrays

When you clone a single dimensional array, such as Object[], a “deep copy” (i.e 2 separate copies are maintained not referenced to same memory location) is performed with the new array containing copies of the original array’s elements as opposed to references.

public static void main(String args[]) 
    {
        int intArray[] = {1,2,3};
          
        int cloneArray[] = intArray.clone();
          
        // will print false as deep copy is created
        // for one-dimensional array
        System.out.println(intArray == cloneArray);
          
        for (int i = 0; i < cloneArray.length; i++) {
            System.out.print(cloneArray[i]+" ");
        }
    }
Output:

false
1 2 3

A clone of a multi-dimensional array (like Object[][]) is a “shallow copy” however, which is to say that it creates only a single new array with each element array a reference to an original element array, but subarrays are shared.

public static void main(String args[]) 
    {
        int intArray[][] = {{1,2,3},{4,5}};
          
        int cloneArray[][] = intArray.clone();
          
        // will print false
        System.out.println(intArray == cloneArray);
          
        // will print true as shallow copy is created
        // i.e. sub-arrays are shared
        System.out.println(intArray[0] == cloneArray[0]);
        System.out.println(intArray[1] == cloneArray[1]);
          
    }

Using System.arraycopy()

We can also use System.arraycopy() Method. The system is present in java.lang package. Its signature is as : 

public static void arraycopy(Object src, int srcPos, Object dest,int destPos, int length)

Where:

1. src denotes the source array. 
2. srcPos is the index from which copying starts.
3. dest denotes the destination array
4. destPos is the index from which the copied elements are placed in the destination array.
5. length is the length of the subarray to be copied. 

      int arr1[] = { 0, 1, 2, 3, 4, 5 };
      int arr2[] = { 5, 10, 20, 30, 40, 50 };
      // copies an array from the specified source array
      System.arraycopy(arr1, 0, arr2, 0, 1);

Using Arrays.copyOf( )

If you want to copy the first few elements of an array or full copy of the array, you can use this method. Its syntax is as:

public static int[] copyOf​(int[] original, int newLength) 

        import java.util.Arrays;
        //Example
        int a[] = { 1, 8, 3 };
        // Create an array b[] of same size as a[]
        // Copy elements of a[] to b[]
        int b[] = Arrays.copyOf(a, 3);

Using Arrays.copyOfRange()

This method copies the specified range of the specified array into a new array.

public static int[] copyOfRange​(int[] original, int from, int to)

Where,

1. original − This is the array from which a range is to be copied, 
2. from       − This is the initial index of the range to be copied, 
3. to            − This is the final index of the range to be copied, exclusive.

         import java.util.Arrays;
         int a[] = { 1, 8, 3, 5, 9, 10 };
 
        // Create an array b[]
        // Copy elements of a[] to b[]
        int b[] = Arrays.copyOfRange(a, 2, 6);

Overview of the above methods: 

• Simply assigning reference is wrong
• The array can be copied by iterating over an array, and one by one assigning elements.
• We can avoid iteration over elements using clone() or System.arraycopy()
• clone() creates a new array of the same size, but System.arraycopy() can be used to copy from a source range to a destination range.
• System.arraycopy() is faster than clone() as it uses Java Native Interface [Todo:what is it (Different from JNI)? how enhance performance](Source : StackOverflow)
• If you want to copy the first few elements of an array or a full copy of an array, you can use Arrays.copyOf() method.
• Arrays.copyOfRange() is used to copy a specified range of an array. If the starting index is not 0, you can use this method to copy a partial array.

Advantages of using arrays:

• Arrays allow random access to elements. This makes accessing elements by position faster.
• Arrays have better cache locality that can make a pretty big difference in performance.
• Arrays represent multiple data items of the same type using a single name.

Disadvantages of using arrays: 

• You can’t change the size i.e. once you have declared the array you can’t change its size because of static memory allocated to it. 
• Insertion and deletion are difficult as the elements are stored in consecutive memory locations and the shifting operation is costly too

Applications on Array

1. Array stores data elements of the same data type.
2. Arrays can be used for CPU scheduling.
3. Used to Implement other data structures like Stacks, Queues, Heaps, Hash tables, etc.