Java: A two dimensional array is stored in column-major or row-major order?

Solution 1:

Java doesn't have multi-dimensional arrays. It has arrays of arrays. So for instance,

int[][]

...is an array of int[] (and of course int[] is an array of int).

Consequently, Java is neither column-major nor row-major order (but see note below about how to read a[2][3]), because while a given array's entries are stored in a contiguous block of memory, the subordinate arrays those entries point to are object references to completely separate, unrelated blocks of memory. This also means that Java's arrays of arrays are inherently jagged: The entry at [0] might refer to a 3-slot array, the one at [1] might refer to a 4-slot array, [2] might not refer to an array at all (it could have null), and perhaps [3] refers to a 6-slot array.

A picture is worth 1k-24 words and all that:

                         +−−−−−−−−+
                   +−−−−>| int[]  |
+−−−−−−−−−−−+      |     +−−−−−−−−+
|  int[][]  |      |     | 0: int |
+−−−−−−−−−−−+      |     | 1: int |
| 0: int[]  |−−−−−−+     | 2: int |
| 1: int[]  |−−−−−−+     +−−−−−−−−+
| 2: null   |      |
| 3: int[]  |−−+   |     +−−−−−−−−+
+−−−−−−−−−−−+  |   +−−−−>| int[]  |
               |         +−−−−−−−−+
               |         | 0: int |
               |         | 1: int |
               |         | 2: int |
               |         | 3: int |
               |         +−−−−−−−−+
               |
               |         +−−−−−−−−+
               +−−−−−−−−−| int[]  |
                         +−−−−−−−−+
                         | 0: int |
                         | 1: int |
                         | 2: int |
                         | 3: int |
                         | 4: int |
                         | 5: int |
                         +−−−−−−−−+

Once you know that, you know that (say) a[2][3] means "Get the array referenced by the entry at index 2 of a, then get the entry referenced by index 3 of that subordinate array." I think of it as fairly similar to row-major order, but it's not quite the same thing.

Solution 2:

In Java, you only have one dimensional arrays.

2D arrays are basically just one dimensional arrays of one dimensional arrays.

int[ ][ ] table;

table = new int[3][ ];

table[0] = new int[5];

table[1] = new int[5];

table[2] = new int[5];

Solution 3:

Neither. What we may sometimes think of as two-dimensional array in Java is actually an array of references to arrays. It's not stored linearly in memory.

The Java Language specification notes this in the introduction:

The language supports arrays of arrays, rather than multidimensional arrays.

This has several implications.

• Arrays of arrays can be jagged -- member arrays can have different lengths.
• The members of an outer array are references, and can be null.
• Cloning an outer array is shallow -- the member arrays are shared between the original and the clone.

From the JLS, section 10.2, "Array Variables":

A single variable of array type may contain references to arrays of different lengths, because an array's length is not part of its type.

From the JLS, section 10.7, "Array Members":

A clone of a multidimensional array is shallow, which is to say that it creates only a single new array. Subarrays are shared.