To this point, we've represented collections of data using data structures in which objects contain references to other objects. Traversal of these data structures is done bo following the references (for example, linked list traversal or searching a binary tree). One advantage of these pointer-based data structures is the ability to add in new items, even into the middle of the structure.

However, sometimes we know how many items will be in a data
structure when it is first created. In that case, we might just
want to set up all the references at once. For example, we
might know that we have 12 months in a year, so we'd like to
create 12 references to `Month`

objects, and be able
to go to any month. This kind of data structure is provided by
the **array**, a concept built into partically all
languages, including Java.

Suppose we already have a class `Month`

whose
constructor takes the name of the month and the number of days
in the month.

Month months[]; Month[] months;

These two are equivalent, and both mean that
`months`

is a reference to an **array**
of `Month`

references.

months = new Month[12];This creates an array of 12

`Month`

references. Note
that it's NOT an array of objects, but an array of references.
Having created the array, we can refer to the individual items by number. Since we created 12 month references, we can access them using the index values 0-11. For example,

months[0] = new Month("January", 31); months[6] = new Month("July", 31); months[0].getName() => "January" months[6].numDays() => 31 months[5].getName() => Null pointer exception months[12].getName() => Array index out of bounds exception

Why? Let's see what it looks like in memory.

This is a **contiguous** memory block of
`Month`

references. The offsets aren't stored in
memory; they are just the "distance" from the start of the array
to each slot.

When we ask for the *i*^{th} entry, Java looks
in the position that is *i* slots down from the start of
the array. If *i* is bigger than the size of the array,
an exception occurs.

Suppose we had created all 12 month objects and initialized the month array completely. We could write a procedure to compute the number of days in a year as follows:

int daysInYear(Month[] calendar) { int total = 0; // days up to, but not including, month i int i = 0; while (i < 12) { total += calendar[i].numDays(); i++; } }

Each `Month`

object could contain an array of
`Day`

's, where each day might contain a list of
appointments:

public class Month { Day[] days; String name; int daysInMonth; public Month(String name, int daysInMonth) { this.name = name; this.daysInMonth = daysInMonth; days = new Day[daysInMonth]; } public int numDays() { return daysInMonth; } public String getName() { return name; } public Day getDay(int date) { if (days[date] == null) days[date] = new Day(name, date); return days[date]; } }

Sometimes, it's convenient to think of a data structure as a grid. For example, the positions on a checkerboard or the pixels on a graphics display. For this, arrays of arrays are convenient.

For example, we might create a checkerboard as an array of 8
rows, where each row contains 8 positions. We can use an
`int`

in each position, where

- 0 = empty
- 1 = red piece
- 2 = black piece

int[][] checkerboard = new int[8][8];This creates an array of arrays of

`int`

's. If we
wanted, we could also create a calendar where each array entry was
an array of `Day`

references.
Day[][] calendar = new Day[12][];This creates an array of 12 arrays of

`Day`

references;
the number for each month is left unspecified. Now,
calendar[0] = new Day[31]; calendar[1] = new Day[28]; ...Sometimes, it's useful to find the length of an array:

calendar.length => 12 calendar[1].length => 28

Matrices are useful in many computer applications. For example, in graphics, matrices are used to render perspective drawings of shapes in a scene.

An *m* × *n* matrix consists of *m* rows and
*n* columns. For example, this is a 3×2 matrix.

We can represent a matrix as an array of *m* rows, where
each row is an array of *n* numbers.

double[][] x = new double[3][2]; x[0][0] = 2; x[0][1] = 3; x[1][0] = 1; ...

A common operation performed on matrices is the
**transpose**, which interchanges the rows and
columns. For example,

double[][] transpose(double[][] x) { int m = x.length; int n = x[0].length; double[][] y = new double[n][m]; int i = 0; while (i < m) { int j = 0; while (j < n) { y[j][i] = x[i][j]; j++; } i++; } return y; }

This procedure uses **nested loops**, one loop
inside another. Each loop has a loop counter, a continuation
test, and a statement to be executed to modify the loop counter at
the end of each iteration.

Since these kinds of loops are so typical, Java provides the
`for`

loop, which is no more powerful than the
`while`

loop, but is more compact.

for (int i = 0; // loop initialization i < m; // test for continuation i++) // statement executed at the end of each iteration for (int j = 0; j < n; j++) y[j][i] = x[i][j];could replace the nested loops in the preceding example.

Given two arrays of doubles (that are the same length), we can define their dot product as the sum of the products of the corresponding entries. For example,

[2 3 1] · [7 4 0] = 2 · 7 + 3 · 4 + 1 · 0 = 26As a procedure,

double dotProduct(double[] a, double[] b) { int result = 0; for (int i = 0; i < a.length; i++) result += a[i]*b[i]; return result; }

Matrix multiplication of an *m* × *r* matrix
*A* and an *r* × *n* matrix *B* is
defined as the *m* × *n* matrix *C* such that
each entry

For example,C[i][j] = the dot product of rowiofAand columnjofB.

To write a procedure for this, we can use the transpose and dot
product: (we **assume** that the number of rows of
`b`

is the same as the number of columns of
`a`

)

double[][] multiply(double[][] a, double[][] b) { double[][] c = new double[a.length][b[0].length]; double[][] bt = transpose(b); for (int i = 0; i < a.length; i++) for (int j = 0; j < bt.length; j++) c[i][j] = dotProduct(a[i], bt[j]); return c; }

Similarly, one could define procedures for other matrix
operations, such as Gaussian elimination, and put all of these
together in a `Matrix`

class.

Kenneth J. Goldman Last modified: Tue Jun 10 14:29:12 CDT 1997