Copyright © 1997 Kenneth J. Goldman

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 ith 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();

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) { = 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];

Multi-dimensional arrays

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

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

Example: Matrix ADT

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.

The declaration might be:
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,

Let's write a procedure

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];

   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 example,
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 = 26
As 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

C[i][j] = the dot product of row i of A and column j of B.
For example,

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