Espresso: A Concentrated Introduction to Java
Summary: We consider one of the central building blocks for data structures: the Array. Arrays group values and permit fast access by numeric index.
Prerequisites: Basics of Java. For loops.
Contents:
As you build larger and larger programs, you will soon find that you have many situations in which you need to group large amounts of similar data. For example, in a grading program, you may need to group students and, for each student, you may need to group grades. Because grouping data is at the center of so many programs, computer scientists study different ways to group data.
We begin with the central philosophy of arrays. Arrays group data of the same type, and they provide access to the data by a number that indicates their position within the group. If we want to use specialized terminology, we say that arrays are homogenous, indexed collections. We use the term collection to generically indicate a data grouping.
What operations do we expect to have for such a collection?
Because arrays are both simple and central, we also expect most of these operations to be comparatively quick (and, except for the case of creating a collection, to take an amount of time or computation independent of the number of values in the array).
To provide fast access to elements, most languages store arrays as a contiguous area of memory. This means that elements are stored one immediately after another, with no gaps between them, in memory. Thus, if the array starts at memory location l, and each value in the array takes space s, and the indices start at 0, then the value in position i can be found at memory location l+is. Note that all values in the array take the same amount of space since all values have the same data type.
In Java, arrays have a special syntax.
The type of an array is specified by giving the type of the
elements followed by an open square bracket and a close square bracket. So
for example, the type of an array of integers is int[] and
the type of an array of strings is String[].
We most typically construct an array with the new
operator, followed by the type of each element, an open bracket, an
integer that gives the size of the array, and a close bracket.
To create an array of five integers called grades, we
would write
int[] grades = new int[5];
Similarly, to create an array of ten objects in class Student,
we would write
Student[] students = new Student[10];
We can also initialize an array during construction by omitting the array size and following the right bracket with a sequence of values separated by commas and surrounded by curly braces. In this case, the java compiler will count the number of elements provided and construct an array of that size. For example, to create an array of the names Jane, Jack, Julie, and John, we could write
String[] names = new String[] { "Jane", "Jack", "Julie", "John" };
Similarly, to create an array of the grades 98, 78, 85, and 90, we could write
int[] grades = new int[] { 98, 78, 85, 90 };
String[] names = { "Jane", "Jack", "Julie", "John" };
int[] grades = { 98, 78, 85, 90 };
This is similar to the syntax shortcut that is allowed when constructing
a single string. Recall that we can write either of the following:
String greeting = "Hello";
String greeting = new String("Hello");
These shortcuts are allowed for arrays and strings in particular because
they are so frequently used.
To obtain the number of values in an array, we use the name of the
array, followed by a period, followed by the keyword length.
For example,
pen.println("There are " + students.length + " students.");
To get a particular value in the array, we use the name of the array, followed by an open bracket, followed by an expression that gives the index, followed by a close bracket. For example, here is some simple code to print all the names in the array of names declared above.
for (int i = 0; i < names.length; i++) {
pen.println(names[i]);
} // for
Notice that in Java, array indices always start at 0. Thus, if an array has
n elements, the elements are numbered from 0 to (n-1). This
gives rise to the idiom above, in which the for-loop counter runs
from 0 to the element before grades.length. As you
might guess from the term idiom, this usage is very common.
Similarly, to set a particular value in the array, we put the name of the array, followed by an open bracket, followed by an expression that gives the index, followed by a close bracket as the variable on the left-hand side of an assignment statement. For example, here is some code that increments all the grades in the class by 5.
for (int i = 0; i < grades.length; i++) {
grades[i] = grades[i] + 5;
} // for
Two-dimensional arrays can be used to store tables of data, in which each element in the table has the same data type. Thus, 2D arrays are very similar to matrices.
The syntax for using 2D arrays is a direct extension of the syntax for 1D arrays. To declare an n x m array of integers, where n is the number of rows, and m is the number of columns, use
int[][] my2DArray = new int[n][m];
To access the value in row i, column j of a 2D array use
int n = my2DArray[i][j];
Be aware that 2D array indices start at 0, just as 1D array indices
do. Thus, the upper-left array element is my2DArray[0][0], and the
lower-right element is my2DArray[n-1][m-1]. (Note that this
differs from the standard notation for matrices.)