2.1.1 Arrays

An array is an indexed sequence $s_0, s_1, s_2, ..., s_n$, $n>=0$ of data values of fixed length. In contrast to more general representations for sequences an array object cannot grow or shrink. It has a specific length $n>=0$ when it is created and retains this length during its entire lifetime. Java arrays are very different than C++ arrays; they are much closer to APArray objects in the AP Computer Science libraries. A Java array is an object that supports the the same high-level operations on arrays as C++.

Every array in Java has a declared type $T$[] asserting that all elements of the array have type $T$. All of the primitive operations on arrays in Java preserve the declared types attached to arrays. Given an array a of type $T$[], the expresssion a[$i$] extracts the $i$th element of the array, which is a value of type $T$. Array indexing begins with the integer value 0 as in C++. Hence, an array of length $n$ has valid indices of $0, 1, ..., n-1$.

Finger Exercise Enter the following array defintion in the DrJava Interactions pane.

int[] a = new int[]{0, 1, 2, 3};

This statement defines an int array a containing four elements: 0, 1, 2, 3. Now evaluate the following expressions:

a
a[0]
a[3]
a[4]

Did you get the results that you expected? The printed value for a is not very informative since it prints a cryptic abbreviation for the type of a (the '[' symbol means ``array-of''l and 'B' means int) followed by the hashcode for the object.^2.1 Unfortunately, Java array classes do not override the toString() method to produce more readable printed output.

The assignment operator = is used to update array elements. Given an array a of type $T$[], the statement

a[$i$] = $e$;

updates the value of the $i$th element to the value of the expression $e$. The values of all other elements of a remain unchanged.

Finger Exercise Continue the preceding exercise by entering the following statement in the interactions window (assuming that a has been defined as shown above):

a[0] = 17;

Now type the expression

a[0]

Did you get the answer that you expected?

In Java, arrays of every type are built into the language. If you define a class or interface $C$, then the array type $C$[] is automatically supported by Java. Every array type is a subtype of type Object, but array types cannot be extended.

If a Java variable has type $T$[] for some primitive or object type $T$ then it can only be bound to arrays of type $U$[] where U is a subtype of T. In the common case the types T and U are identical. Primtive types have no proper subtypes, so an exact match is required in this case.

Every Java array has a int field length that contains the length of the array.

Finger Exercise Continue the preceding exercise by evaluating the following expression in the Interactions pane:

a.length

Did you get the answer that you expected?

Since Java arrays are objects, a Java array value is actually a reference to an array. Hence, a variable of type $T$[] in Java can have the value null. A variable of type $T$[] can appear on the left-hand side of an assignment

a = $e$

where $e$ is any expression of type $T$.

Since array values are references to arrays, two variables can be bound to exactly the same array. If array variables a and b are bound to the same array object, then updating the array a

a[i] = e;

changes the value of b[i].

Finger Exercise Continue the preceding exercise by entering the following sequence of statements and expressions in the Interactions pane:

int[] b = a;
b[0]
b[0] = 5;
a[0]

Did you get the resulsts that you expected?

Arrays are allocated in Java using the new statement just like other objects. The array form is

new T[length]

where T is any type and length is an expression that evaluates to a non-negative int. Arrays can have length 0. Each element of the array is set to the `zero'' value of the declared type T. If T is an object type, the initial value of each element is null. Hence, the expression

new String[1000]

allocates an array of 1000 String elements all bound to null.

Java has alternate form for constructing an array called an anonymous array. The expression

new T[] { $v_0, ... v_{n-1}$}

allocates an array of length $n$ of type T containing the specified sequence of elements.

Java uses two mechanisms to enforce the declared type T[] of an array object. First, when an array T[] is allocated, all of the initial element values must be of type T. Second, when an array object a of type T[] is updated by an assignment

a[$i$] = $e$

Java confirms that the the new value e for the $i$th element belongs to the type T. During program execution, the Java virtual machine confirms the the value $e$ belongs to type T each time that the assignment is executed.

The array-assignment check must be performed at run-time because an array object of type S[] can be stored in a local variable or field of type T[] where S is a subtype of T. Hence, in the preceding array assignment, the declared (static) type T of e could match the declared type T[] of the array variable a, yet the assignment could fail at run-time because the value of a is an array of type S[] where S is a proper subtype of T.

The Java type system permits an array variable of type T[] to be bound to an array A of type S[] provided S is subtype of T. This property of the Java type system is called covariant subtyping. Note that covariant subtyping implies that the array type Object[] is a supertype for all object array types, which permits arrays to be treated polymorhically in many situations.