Dimensions for two-dimensional array creation in Java seem backwards

Question

As far as I understand a two-dimensional array in java is an array of arrays. Analogously to the usual array notation I would expect this to mean that

int[][]

is actually

(int[])[]

(An array of int arrays). Thus I would expect the length of the array

int[][] array = new int[2][3]; // (int[2])[3] 

to be 3 (as it would be an array of length 3 of arrays of length 2). It does however appear to be the other way round.

I tried to find an explanation for this, but was unable to. I found many posts explaining how to initialize multidimensional arrays and that they are arrays of arrays but I was unable to find any explanation of why the order of the indices works out this way.

My only theory is that people find it more natural to iterate over the left index first and Java is built in a way such that this operation is more efficient so the developers made this choice very deliberately.

I am thankful for any source confirming this interpretation or any other reasons why it works out this way.

---

edit: Since there seems to be some confusion as to why anyone would ever believe using the indices the other way round would be a good idea, here is some clarification:

For a type T the expression new T[5] usually yields an array of size 5. The type int[] seems to be a perfectly good type, however Java does not allow me to say new (int[])[5] and instead forces me to initiate this array of arrays using new int[5][]. I was looking for a reason why Java would do that to me (and got one).

---

One other thing I would like to add with respect to the (very good) answers for anyone thinking like me: In a world where nobody had ever thought about two-dimensional arrays and you were allowed to create arrays of type int[] as you would create any other array, the following might be perfectly legal code.

    int[][] = new (int[])[5];
    int[] firstArray = new int[3];
    int[0] = firstArray;
    int[0][2] = 1; // last element of first array
    int[0][4] = 2; // IndexOutOfBoundsException, trying to access 5th element of firstArray

This would of course be utterly confusing so I am glad that multidimensional arrays get a special treatment.

Answer 1

You may think of a two dimensional array in Java as an array of arrays. Consider the following general 2D array of numbers:

1 2 3
4 5 6
7 8 9

We could define this array as:

int[][] array = new int[][] {{1,2,3}, {4,5,6}, {7,8,9}};

Or, we could use an empty constructor, and then populate the individual values:

int[][] array = new int[3][3];
array[0][0] = 1;
array[0][1] = 2;
// etc.

But to better understand how 2D arrays in Java work, consider the following approach:

int[][] array = new int[3][];
arr[0] = new int[] {1, 2, 3};
arr[1] = new int[] {4, 5, 6};
arr[2] = new int[] {7, 8, 9};

Hopefully it is clear what a 2D array actually is; it is an array of arrays, so we may visualize this as:

[ ] -> [1, 2, 3]
[ ] -> [4, 5, 6]
[ ] -> [7, 8, 9]

That is, each element in the first index of the array, of size 3, corresponding to the rows, points to another 1D array, corresponding to the columns. Note that in Java a 2D array can be jagged, meaning that we could also have done this:

int[][] array = new int[3][];
arr[0] = new int[] {1, 2, 3, 4, 5};
arr[1] = new int[] {1, 2, 3};
arr[2] = new int[] {7, 7, 7};

To address the concern raised by @Henry in a comment below, that the size of the leftmost portion of the above 2D array is 3 agrees with what we see when we draw it out. Namely, we see a 1D array with 3 buckets, each of which points to another 1D array of some size.

Answer 2

The reason for this is the importance of array accesses. You have an array of arrays (int[][]). You then retrieve an array from it (int[]). You then retrieve an element from that (int).

There are two ways of doing this. The first is most important:

for (int i = 0; i < matrix.length; i++) {
    int[] row = matrix[i];
    for int j = 0; j < row.length; j++) {
        int element = row[j];
    }
}

It would be absurd to have to use int[] row = matrix[][i]; in the first example, since the convention is to have array[i] represent the first element of array. In this case, the first element of array is a row, not an element.

The same index ordering is applied consistently throughout.

---

This is also consistent with the fact that you can have a matrix-like object of strange dimensions with an Object[] array. Perhaps one element of that array will be an int[][][] while the next will be an int[]. It would be a bit odd to have to somehow figure out whether to put array[][][][i] or array[][i] when you don't know the dimensionality of subarray i and the subarrays don't even necessarily have a consistent number of dimensions.

Answer 3

An expression like new int[2][5] will create an outer array of length 2, with each element referencing an array of length 5, so a total of 3 arrays are created. This is well-documented in the Java Language Specification, Example 15.10.2-2. Multi-Dimensional Array Creation:

The declaration:

float[][] matrix = new float[3][3];

is equivalent in behavior to:

float[][] matrix = new float[3][];
for (int d = 0; d < matrix.length; d++)
    matrix[d] = new float[3];

It does not mean (int[2])[5], i.e. an array of 5 referencing arrays of 2.

Because of that, the expression to lookup values is evaluated left-to-right, e.g. x[2][5] means (x[2])[5], i.e. in int[][] x variable, lookup x[2], which is an int[], and in that array lookup value at index 5.

int[][] x = new int[9][9];
// z = x[2][5]
int[] y = x[2];
int z = y[5];