Java Notes

Two-dimensional arrays as arrays of arrays

Arrays of arrays

Java builds multi-dimensional arrays from many one-dimensional arrays, the so-called "arrays of arrays" approach.

There are a couple of interesting consequences of this: Rows may be different sizes. Also, each row is an object (an array) that can be used independently.

Multi-dimensional arrays are built from multiple one-dimensional arrays

As with all arrays, the new keyword must be used to allocate memory for an array. For example,

int[][] a = new int[2][4];

This two-dimensional array will have two rows and four columns.

This actually allocates 3 objects: a one-dimensional array of 2 elements to hold each of the actual row arrays, and a two one-dimensional arrays of 4 elements to represent the contents of the rows.

     +-----+    +-----+-----+-----+-----+
     |a[0] | -> | [0] | [1] | [2] | [3] |
     |     |    +-----+-----+-----+-----+
     +-----+
     |     |    +-----+-----+-----+-----+
     |a[1] | -> | [0] | [1] | [2] | [3] |
     +-----+    +-----+-----+-----+-----+

Processing 2-dimensional arrays using .length

Notice in the following example how the rows are handled as separate objects. For example,

int[][] a2 = ...;

// Print array even tho we don't know the original size.
for (int r=0; r < a2.length; r++) {
    for (int c=0; c < a2[r].length; c++) {
        System.out.print(" " + a2[r][c]);
    }
    System.out.println("");
}

Trick: Ignoring the zeroth row

Sometimes you want to use natural input values as an index, the real values that that data has instead of starting with zero. Let's take the case of data that starts with the value 1, like the day of the month. The standard approach is to subtract one from every day value that's used as an index. This is annoying and error prone. Another way to do handle this case is to declare the array with an extra element, eg, 32 if dealing with the days in the month, then ignoring the zeroth element. If you're dealing with a two dimensional array, for example the accidents array from the previous page, you can even deallocate the first row so there won't be any possibility of referencing the zeroth day. For example,

static final int DAYS  = 32;
static final int HOURS = 24;
. . .
int[][] accidents = new int[DAYS][HOURS];
accidents[0] = null;

Because two-dimensional arrays are stored by row, you can do this. You can use the trick of allocating more columns to use the natural data, but you can't deallocate a column.

Ragged arrays - Uneven rows

One consequence of arrays of arrays is that each row can be a different size. For example, we could create a lower triangular array, allocating each row "by hand" as follows. Note how new can be used with only the row dimension.

int[][] tri;

//... Allocate each part of the two-dimensional array individually.
tri = new int[10][];        // Allocate array of rows
for (int r=0; r < tri.length; r++) {
    tri[r] = new int[r+1];  // Allocate a row
}

//... Print the triangular array (same as above really)
for (int r=0; r<tri.length; r++) {
    for (int c=0; c<tri[r].length; c++) {
        System.out.print(" " + tri[r][c]);
    }
    System.out.println("");
}

Triangular array example - distance table

A good example of a triangular array is one of those tables of the distance between two cities that is often in the front of some road atlas covers. The distance from New York to Chicago is the same as the distance from Chicago to New York - there's not need to have it twice in the same table - at least if you have a need for that remaining space.

Commentary: Two ways to store multi-dimensional arrays

There are two ways to implement 2-dimensional arrays. Many languages reserve a block of memory large enough to hold all elements of the full, rectangular, array (number of rows times number of columns times the element size). Some languages, like Java, build multi-dimensional arrays from many one-dimensional arrays, the so-called "arrays of arrays" approach. C++ supports both styles.