Array Data Structure in Java
An Array is a data structure to store elements of same type. Each element can be accessed by index. Hence random access is possible using Array.
An array of 10 elements with index starting at 0
Arrays can be of any dimensions. Single and two dimensional arrays are commonly used. Two dimensional arrays are used for mathematical calculations (for example, Matrix).
Several abstract data structures like Hashtable, ArrayList uses arrays as the underlying data structure.
Working with Arrays
To initialize an array the size has to be given up front.
Elements can be added to an array using the numeric index.
|
1 2 3 4 5 6 |
int[] numArr = new int[5]; for(int i=0; i < numArr.length; i++) { numArr[i] = i; } |
Accessing the arrays can done using the random index. Hence the operation is very fast and is O(1) complexity. However searching for a specific element in an array is not going to be so efficient. The elements has to iterated over to complete the search. Hence it is O(N) linear time complexity.
|
1 2 3 4 5 6 7 8 |
int val = numArr[3]; System.out.println("Val retrieved: "+val); for(int i=0; i < numArr.length; i++) { if(numArr[i] == 4) { System.out.println("Searched value found at index : "+i); } } |
Similarly, copying elements of an array to an another array is also going to be O(N) Linear time complexity. Since entire array has to iterated over and copy each element to new array.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
package com.rayfocus.datastructures; public class ArrayDS { public static void main(String args[]) { int[] numArr = new int[5]; // Array has to initialized // add items to Array for(int i=0; i < numArr.length; i++) { numArr[i] = i; } // Accessing the Array using index value // O(1) Complexity; Very fast int val = numArr[3]; System.out.println("Val retrieved: "+val); // Search for an element in Array // O(N) Linear time Complexity; for(int i=0; i < numArr.length; i++) { if(numArr[i] == 4) { System.out.println("Searched value found at index : "+i); } } // Copying elements of Array to another Array // It is O(N) linear time complexity int[] numArrCopy = new int[10]; for(int i=0; i < numArr.length; i++) { numArrCopy[i] = numArr[i]; // Need to iterate and copy values to new Array } } } |
Summary
Array data structure is a good choice when,
- The number of elements to be added is well known.
- Only the same data type has to be stored together.
- The elements are going to be added and retrieved using the random index value. It is O(1) complexity.
Array is not so efficient when,
- The number of elements to be added is not known.
- There is a need to create array of bigger size. Each value has to be copied one by one.
- Constructing a new array from an existing one is O(N) operation.
- Specific element has to searched. Search operation in Array is O(N) complexity.
References
Array representation image : https://docs.oracle.com/javase/tutorial/figures/java/objects-tenElementArray.gif
