This chapter is from the book
This chapter is from the book
This chapter is from the book
3.4 Arrays
An array is a data structure that defines an indexed collection of a fixed number of homogeneous data elements. This means that all elements in the array have the same data type. A position in the array is indicated by a non-negative integer value called the index. An element at a given position in the array is accessed using the index. The size of an array is fixed and cannot be changed after the array has been created.
In Java, arrays are objects. Arrays can be of primitive data types or reference types. In the former case, all elements in the array are of a specific primitive data type. In the latter case, all elements are references of a specific reference type. References in the array can then denote objects of this reference type or its subtypes. Each array object has a public final field called length, which specifies the array size (i.e., the number of elements the array can accommodate). The first element is always at index 0 and the last element at index n – 1, where n is the value of the length field in the array.
Simple arrays are one-dimensional arrays—that is, a simple list of values. Since arrays can store reference values, the objects referenced can also be array objects. Thus, multidimensional arrays are implemented as array of arrays.
Passing array references as parameters is discussed in §3.5, p. 72. Type conversions for array references on assignment and on method invocation are discussed in §7.7, p. 309.
Declaring Array Variables
A one-dimensional array variable declaration has either of the following syntaxes:
element_type[] array_name;
or
element_type array_name[];
where element_type can be a primitive data type or a reference type. The array variable array_name has the type element_type[]. Note that the array size is not specified. As a consequence, the array variable array_name can be assigned the reference value of an array of any length, as long as its elements have element_type.
It is important to understand that the declaration does not actually create an array. Instead, it simply declares a reference that can refer to an array object. The [] notation can also be specified after a variable name to declare it as an array variable, but then it applies to just that variable.
int anIntArray[], oneInteger; Pizza[] mediumPizzas, largePizzas;
These two declarations declare anIntArray and mediumPizzas to be reference variables that can refer to arrays of int values and arrays of Pizza objects, respectively. The variable largePizzas can denote an array of Pizza objects, but the variable oneInteger cannot denote an array of int values—it is a simple variable of the type int.
An array variable that is declared as a field in a class, but is not explicitly initialized to any array, will be initialized to the default reference value null. This default initialization does not apply to local reference variables and, therefore, does not apply to local array variables either (§2.4, p. 42). This behavior should not be confused with initialization of the elements of an array during array construction.
Constructing an Array
An array can be constructed for a fixed number of elements of a specific type, using the new operator. The reference value of the resulting array can be assigned to an array variable of the corresponding type. The syntax of the array creation expression is shown on the right-hand side of the following assignment statement:
array_name = new element_type[array_size];
The minimum value of array_size is 0; in other words zero-length arrays can be constructed in Java. If the array size is negative, a NegativeArraySizeException is thrown at runtime.
Given the declarations
int anIntArray[], oneInteger; Pizza[] mediumPizzas, largePizzas;
the three arrays in the declarations can be constructed as follows:
anIntArray = new int[10]; // array for 10 integers mediumPizzas = new Pizza[5]; // array of 5 pizzas largePizzas = new Pizza[3]; // array of 3 pizzas
The array declaration and construction can be combined.
element_type1[] array_name = new element_type2[array_size];
In the preceding syntax, the array type element_type2[] must be assignable to the array type element_type1[] (§7.7, p. 309). When the array is constructed, all of its elements are initialized to the default value for element_type2. This is true for both member and local arrays when they are constructed.
In the next examples, the code constructs the array, and the array elements are implicitly initialized to their default values. For example, all elements of the array anIntArray get the value 0, and all elements of the array mediumPizzas get the value null when the arrays are constructed.
int[] anIntArray = new int[10]; // Default element value: 0 Pizza[] mediumPizzas = new Pizza[5]; // Default element value: null
The value of the field length in each array is set to the number of elements specified during the construction of the array; for example, mediumPizzas.length has the value 5.
Once an array has been constructed, its elements can also be explicitly initialized individually—for example, in a loop. The examples in the rest of this section make use of a loop to traverse the elements of an array for various purposes.
Initializing an Array
Java provides the means of declaring, constructing, and explicitly initializing an array in one declaration statement:
element_type[] array_name = { array_initialize_list };
This form of initialization applies to fields as well as to local arrays. The array_initialize_list is a comma-separated list of zero or more expressions. Such an array initializer results in the construction and initialization of the array.
int[] anIntArray = {13, 49, 267, 15, 215};
In this declaration statement, the variable anIntArray is declared as a reference to an array of ints. The array initializer results in the construction of an array to hold five elements (equal to the length of the list of expressions in the block), where the first element is initialized to the value of the first expression (13), the second element to the value of the second expression (49), and so on.
Pizza[] pizzaOrder = { new Pizza(), new Pizza(), null };
In this declaration statement, the variable pizzaOrder is declared as a reference to an array of Pizza objects. The array initializer constructs an array to hold three elements. The initialization code sets the first two elements of the array to refer to two Pizza objects, while the last element is initialized to the null reference. The reference value of the array of Pizza objects is assigned to the reference pizzaOrder. Note also that this declaration statement actually creates three objects: the array object with three references and the two Pizza objects.
The expressions in the array_initialize_list are evaluated from left to right, and the array name obviously cannot occur in any of the expressions in the list. In the preceding examples, the array_initialize_list is terminated by the right brace, }, of the block. The list can also be legally terminated by a comma. The following array has length 2, and not 3:
Topping[] pizzaToppings = { new Topping("cheese"), new Topping("tomato"), };
The declaration statement at (1) in the following code defines an array of four String objects, while the declaration statement at (2) shows that a String object is not the same as an array of char.
// Array with 4 String objects:
String[] pets = {"crocodiles", "elephants", "crocophants", "elediles"}; // (1)
// Array of 3 characters:
char[] charArray = {'a', 'h', 'a'}; // (2) Not the same as "aha"
Using an Array
The array object is referenced by the array name, but individual array elements are accessed by specifying an index with the [] operator. The array element access expression has the following syntax:
array_name [index_expression]
Each individual element is treated as a simple variable of the element type. The index is specified by the index_expression, whose value should be promotable to an int value; otherwise, a compile-time error is flagged. Since the lower bound of an array index is always 0, the upper bound is 1 less than the array size—that is, array_name.length-1. The ith element in the array has index (i-1). At runtime, the index value is automatically checked to ensure that it is within the array index bounds. If the index value is less than 0, or greater than or equal to array_name.length, an ArrayIndexOutOfBoundsException is thrown. A program can either check the index explicitly or catch the runtime exception (§6.5, p. 230), but an illegal index is typically an indication of a programming error.
In the array element access expression, the array_name can be any expression that returns a reference to an array. For example, the expression on the right-hand side of the following assignment statement returns the character 'H' at index 1 in the character array returned by a call to the toCharArray() method of the String class:
char letter = "AHA".toCharArray()[1]; // 'H'
The array operator [] is used to declare array types (Topping[]), specify the array size (new Topping[3]), and access array elements (toppings[1]). This operator is not used when the array reference is manipulated, such as in an array reference assignment (§7.9, p. 312), or when the array reference is passed as an actual parameter in a method call (§3.5, p. 77).
Example 3.3 shows traversal of arrays using for loops (§6.3, p. 215 and p. 217). A for(;;) loop at (3) in the main() method initializes the local array trialArray declared at (2) five times with pseudo-random numbers (from 0.0 to 100.0), by calling the method randomize() declared at (5). The minimum value in the array is found by calling the method findMinimum() declared at (6), and is stored in the array storeMinimum declared at (1). Both of these methods also use a for(;;) loop. The loop variable is initialized to a start value—0 in (3) and (5), and 1 in (6). The loop condition tests whether the loop variable is less than the length of the array; this guarantees that the loop will terminate when the last element has been accessed. The loop variable is incremented after each iteration to access the next element.
A for(:) loop at (4) in the main() method is used to print the minimum values from the trials, as elements are read consecutively from the array, without keeping track of an index value.
Example 3.3 Using Arrays
public class Trials {
public static void main(String[] args) {
// Declare and construct the local arrays:
double[] storeMinimum = new double[5]; // (1)
double[] trialArray = new double[15]; // (2)
for (int i = 0; i < storeMinimum.length; ++i) { // (3)
// Initialize the array.
randomize(trialArray);
// Find and store the minimum value.
storeMinimum[i] = findMinimum(trialArray);
}
// Print the minimum values: (4)
for (double minValue : storeMinimum)
System.out.printf("%.4f%n", minValue);
}
public static void randomize(double[] valArray) { // (5)
for (int i = 0; i < valArray.length; ++i)
valArray[i] = Math.random() * 100.0;
}
public static double findMinimum(double[] valArray) { // (6)
// Assume the array has at least one element.
double minValue = valArray[0];
for (int i = 1; i < valArray.length; ++i)
minValue = Math.min(minValue, valArray[i]);
return minValue;
}
}
Probable output from the program:
6.9330 2.7819 6.7427 18.0849 26.2462
Anonymous Arrays
As shown earlier in this section, the following declaration statement can be used to construct arrays using an array creation expression:
element_type1[] array_name = new element_type2[array_size]; // (1) int[] intArray = new int[5];
The size of the array is specified in the array creation expression, which creates the array and initializes the array elements to their default values. By comparison, the following declaration statement both creates the array and initializes the array elements to specific values given in the array initializer:
element_type[] array_name = { array_initialize_list }; // (2)
int[] intArray = {3, 5, 2, 8, 6};
However, the array initializer is not an expression. Java has another array creation expression, called an anonymous array, which allows the concept of the array creation expression from (1) to be combined with the array initializer from (2), so as to create and initialize an array object:
new element_type[] { array_initialize_list }
new int[] {3, 5, 2, 8, 6}
This construct has enough information to create a nameless array of a specific type. Neither the name of the array nor the size of the array is specified. The construct returns the reference value of the newly created array, which can be assigned to references and passed as argument in method calls. In particular, the following declaration statements are equivalent:
int[] intArray = {3, 5, 2, 8, 6}; // (1)
int[] intArray = new int[] {3, 5, 2, 8, 6}; // (2)
In (1), an array initializer is used to create and initialize the elements. In (2), an anonymous array expression is used. It is tempting to use the array initializer as an expression—for example, in an assignment statement, as a shortcut for assigning values to array elements in one go. However, this is illegal; instead, an anonymous array expression should be used. The concept of the anonymous array combines the definition and the creation of the array into one operation.
int[] daysInMonth;
daysInMonth = {31, 28, 31, 30, 31, 30,
31, 31, 30, 31, 30, 31}; // Compile-time error
daysInMonth = new int[] {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; // OK
In Example 3.4, an anonymous array is constructed at (1), and passed as an actual parameter to the static method findMinimum() defined at (2). Note that no array name or array size is specified for the anonymous array.
Example 3.4 Using Anonymous Arrays
public class AnonArray {
public static void main(String[] args) {
System.out.println("Minimum value: " +
findMinimum(new int[] {3, 5, 2, 8, 6})); // (1)
}
public static int findMinimum(int[] dataSeq) { // (2)
// Assume the array has at least one element.
int min = dataSeq[0];
for (int index = 1; index < dataSeq.length; ++index)
if (dataSeq[index] < min)
min = dataSeq[index];
return min;
}
}
Output from the program:
Minimum value: 2
Multidimensional Arrays
Since an array element can be an object reference and arrays are objects, array elements can themselves refer to other arrays. In Java, an array of arrays can be defined as follows:
element_type[][]...[] array_name;
or
element_type array_name[][]...[];
In fact, the sequence of square bracket pairs, [], indicating the number of dimensions, can be distributed as a postfix to both the element type and the array name. Arrays of arrays are often called multidimensional arrays.
The following declarations are all equivalent:
int[][] mXnArray; // 2-dimensional array int[] mXnArray[]; // 2-dimensional array int mXnArray[][]; // 2-dimensional array
It is customary to combine the declaration with the construction of the multidimensional array.
int[][] mXnArray = new int[4][5]; // 4 x 5 matrix of ints
The previous declaration constructs an array mXnArray of four elements, where each element is an array (row) of five int values. The concept of rows and columns is often used to describe the dimensions of a 2-dimensional array, which is often called a matrix. However, such an interpretation is not dictated by the Java language.
Each row in the previous matrix is denoted by mXnArray[i], where 0 ≤ i < 4. Each element in the ith row, mXnArray[i], is accessed by mXnArray[i][j], where 0 ≤ j < 5. The number of rows is given by mXnArray.length, in this case 4, and the number of values in the ith row is given by mXnArray[i].length, in this case 5 for all the rows, where 0 ≤ i < 4.
Multidimensional arrays can also be constructed and explicitly initialized using the array initializers discussed for simple arrays. Note that each row is an array that uses an array initializer to specify its values:
double[][] identityMatrix = {
{1.0, 0.0, 0.0, 0.0 }, // 1. row
{0.0, 1.0, 0.0, 0.0 }, // 2. row
{0.0, 0.0, 1.0, 0.0 }, // 3. row
{0.0, 0.0, 0.0, 1.0 } // 4. row
}; // 4 x 4 floating-point matrix
Arrays in a multidimensional array need not have the same length; when they do not, they are called ragged arrays. The array of arrays pizzaGalore in the following code has five rows; the first four rows have different lengths but the fifth row is left unconstructed:
Pizza[][] pizzaGalore = {
{ new Pizza(), null, new Pizza() }, // 1. row is an array of 3 elements.
{ null, new Pizza()}, // 2. row is an array of 2 elements.
new Pizza[1], // 3. row is an array of 1 element.
{}, // 4. row is an array of 0 elements.
null // 5. row is not constructed.
};
When constructing multidimensional arrays with the new operator, the length of the deeply nested arrays may be omitted. In such a case, these arrays are left unconstructed. For example, an array of arrays to represent a room on a floor in a hotel on a street in a city can have the type HotelRoom[][][][]. From left to right, the square brackets represent indices for street, hotel, floor, and room, respectively. This 4-dimensional array of arrays can be constructed piecemeal, starting with the leftmost dimension and proceeding to the rightmost successively.
HotelRoom[][][][] rooms = new HotelRoom[10][5][][]; // Just streets and hotels.
The preceding declaration constructs the array of arrays rooms partially with ten streets, where each street has five hotels. Floors and rooms can be added to a particular hotel on a particular street:
rooms[0][0] = new HotelRoom[3][]; // 3 floors in 1st hotel on 1st street. rooms[0][0][0] = new HotelRoom[8]; // 8 rooms on 1st floor in this hotel. rooms[0][0][0][0] = new HotelRoom(); // Initializes 1st room on this floor.
The next code snippet constructs an array of arrays matrix, where the first row has one element, the second row has two elements, and the third row has three elements. Note that the outer array is constructed first. The second dimension is constructed in a loop that constructs the array in each row. The elements in the multidimensional array will be implicitly initialized to the default double value (0.0D). In Figure 3.1, the array of arrays matrix is depicted after the elements have been explicitly initialized.
double[][] matrix = new double[3][]; // Number of rows. for (int i = 0; i < matrix.length; ++i) matrix[i] = new double[i + 1]; // Construct a row.
)
Figure 3.1 Array of Arrays
Two other ways of initializing such an array of arrays are shown next. The first approach uses array initializers, and the second uses an anonymous array of arrays.
double[][] matrix2 = { // Using array initializers.
{0.0}, // 1. row
{0.0, 0.0}, // 2. row
{0.0, 0.0, 0.0} // 3. row
};
double[][] matrix3 = new double[][] { // Using an anonymous array of arrays.
{0.0}, // 1. row
{0.0, 0.0}, // 2. row
{0.0, 0.0, 0.0} // 3. row
};
The type of the variable matrix is double[][], a two-dimensional array of double values. The type of the variable matrix[i] (where 0 ≤ i< matrix.length) is double[], a one-dimensional array of double values. The type of the variable matrix[i][j] (where 0 ≤ i< matrix.length and 0 ≤ j< matrix[i].length) is double, a simple variable of type double.
Nested loops are a natural match for manipulating multidimensional arrays. In Example 3.5, a rectangular 4 × 3 int matrix is declared and constructed at (1). The program finds the minimum value in the matrix. The outer loop at (2) traverses the rows (mXnArray[i], where 0 ≤ i< mXnArray.length), and the inner loop at (3) traverses the elements in each row in turn (mXnArray[i][j], where 0 ≤ j< mXnArray[i].length). The outer loop is executed mXnArray.length times, or 4 times, and the inner loop is executed (mXnArray.length) × (mXnArray[i].length), or 12 times, since all rows have the same length 3.
The for(:) loop also provides a safe and convenient way of traversing an array. Several examples of its use are provided in §6.3, p. 217.
Example 3.5 Using Multidimensional Arrays
public class MultiArrays {
public static void main(String[] args) {
// Declare and construct the M X N matrix.
int[][] mXnArray = { // (1)
{16, 7, 12}, // 1. row
{ 9, 20, 18}, // 2. row
{14, 11, 5}, // 3. row
{ 8, 5, 10} // 4. row
}; // 4 x 3 int matrix
// Find the minimum value in a M X N matrix:
int min = mXnArray[0][0];
for (int i = 0; i < mXnArray.length; ++i) // (2)
// Find min in mXnArray[i], in the row given by index i:
for (int j = 0; j < mXnArray[i].length; ++j) // (3)
min = Math.min(min, mXnArray[i][j]);
System.out.println("Minimum value: " + min);
}
}
Output from the program:
Minimum value: 5
Sorting Arrays
Sorting implies ordering the elements according to some ranking criteria, usually based on the values of the elements. The values of numeric data types can be compared and ranked by using the relational operators. For comparing objects of a class, the class typically implements the compareTo() method of the Comparable interface. The ordering defined by this method is called the natural ordering for the objects of the class. The wrapper classes for primitive values and the String class implement the compareTo() method (§8.3, p. 350, and §8.4, p. 363, respectively).
The java.util.Arrays class provides many overloaded versions of the sort() method to sort practically any type of array.
An appropriate import statement should be included in the source code to access the java.util.Arrays class. In the next code snippet, an array of strings is sorted according to natural ordering for strings—that is, based on the Unicode values of the characters in the strings:
String[] strArray = {"biggest", "big", "bigger", "Bigfoot"};
Arrays.sort(strArray); // Natural ordering: [Bigfoot, big, bigger, biggest]
The next examples illustrate sorting an array of primitive values (int) at (1), and an array of type Object containing mutually comparable elements (String) at (2). In (3), the numerical values are autoboxed into their corresponding wrapper classes (§8.3, p. 346), but the objects of different wrapper classes and the String class are not mutually comparable. In (4), the numerical values are also autoboxed into their corresponding wrapper classes, but again the objects of different wrapper classes are not mutually comparable. A ClassCastException is thrown when the elements are not mutually comparable.
int[] intArray = {5, 3, 7, 1}; // int
Arrays.sort(intArray); // (1) Natural ordering: [1, 3, 5, 7]
Object[] objArray1 = {"I", "am", "OK"}; // String
Arrays.sort(objArray1); // (2) Natural ordering: [I, OK, am]
Object[] objArray2 = {23, "ten", 3.14}; // Not mutually comparable
Arrays.sort(objArray2); // (3) ClassCastException
Number[] numbers = {23, 3.14, 10L}; // Not mutually comparable
Arrays.sort(numbers); // (4) ClassCastException
Searching Arrays
A common operation on an array is to search the array for a given element, called the key. The java.util.Arrays class provides overloaded versions of the binarySearch() method to search in practically any type of array that is sorted.
An appropriate import statement should be included in the source code to access the java.util.Arrays class. In the code that follows, the return value –3 indicates that the key would have been found at index 2 had it been in the list:
// Sorted String array (natural ordering): [Bigfoot, big, bigger, biggest] // Search in natural ordering: int index1 = Arrays.binarySearch(strArray, "bigger"); // Successful: 2 int index2 = Arrays.binarySearch(strArray, "bigfeet"); // Unsuccessful: -3 int index3 = Arrays.binarySearch(strArray, "bigmouth"); // Unsuccessful: -5
Results are unpredictable if the array is not sorted, or if the ordering used in the search is not the same as the sort ordering. Searching in the strArray using natural ordering when the array is sorted in reverse natural ordering gives the wrong result:
// Sorted String array (inverse natural ordering): [biggest, bigger, big, Bigfoot] // Search in natural ordering: int index4 = Arrays.binarySearch(strArray, "big"); // -1 (INCORRECT)
A ClassCastException is thrown if the key and the elements are not mutually comparable:
int index5 = Arrays.binarySearch(strArray, 4); // Key: 4 => ClassCastException
However, this incompatibility is caught at compile time in the case of arrays with primitive values:
// Sorted int array (natural ordering): [1, 3, 5, 7] int index6 = Arrays.binarySearch(intArray, 4.5);//Key: 4.5 => compile-time error!
The method binarySearch() derives its name from the divide-and-conquer algorithm that it uses to perform the search. It repeatedly divides the remaining elements to be searched into two halves and selects the half containing the key to continue the search in, until either the key is found or there are no more elements left to search.