Why is an ArrayList of ArrayLists not multidimensional?

Question

I recently appeared for an interview in which the interviewer asked me a question regarding Arrays and ArrayList.

He asked me if an array of arrays can be multidimensional, then why is an ArrayList of ArrayList's not multidimensional?

For example:

// Multidimensional
int[][] array = new int[m][n]; 

// Not multidimensional
ArrayList<ArrayList<Integer>> seq = new ArrayList<ArrayList<Integer>>(); 

Can anyone help me to understand this?

Answer 1

Cay S. Horstmann has stated within his book Core Java for the impatient:

There are no two-dimensional array lists in Java, but you can declare a variable of type ArrayList<ArrayList<Integer>> and build up the rows yourself.

due to the fact that ArrayLists can expand and shrink and become jagged rather than multi-dimensional, one could say it is not a two-dimensional array, multi-dimensional meaning fixed rows and columns, hence why I have also stated within the comments Java doesn't have true multi-dimensional arrays but this is outside the scope of your question.

if you're curious as to why I said Java doesn't have true multi-dimensional arrays have a read at the differences between a multidimensional array and an array of arrays in C#?

---

Just to make my answer clearer regarding whether Java has true multi-dimensional arrays or not, I did not say java doesn't have multi-dimensional arrays, I said Java doesn't have true multi-dimensional arrays and as expect the JLS has stated:

A multidimensional array need not have arrays of the same length at each level.

Answer 2

For the same reason the shopping bag I put all my spare shopping bags into is not a multidimensional shopping bag.

If I put a nut in one bag then put that bag in another bag, I have to perform two operations to get the nut.

If I instead put the nut in a two dimensional component tray, I can perform one operation to access it using two indices:

source

Similarly, there is a fundamental difference between a list of lists ( or array of arrays ) and a true two dimensional array - a single operation taking two indices is used to access the elements in a two dimensional array, two operations each taking one index are used to access the elements in a list of lists.

An ArrayList has a single index, so it has a rank of 1. A two dimensional array has two indices, its rank is 2.

note: by 'two dimensional array' I am not referring to a Java array of (references to) arrays, but a two dimensional array as found in other languages such as FORTRAN. Java does not have multidimensional arrays. If your interviewer was specifically referring to Java 'arrays of arrays' then I would disagree with them, as Java's int[][] defines an array of references to arrays of integers, and that requires two dereferencing operations to access the elements. An array of arrays in C for example supports access with a single dereferencing operation so is closer to the multidimensional case.

Answer 3

Looking at it from the other side: you can use lists in the very same way as "multi dimensional" arrays. You only have to replace array[row][column] with someList.get(row).get(column)!

And in the end, java arrays are implemented in similar ways: a two dim matrix is also just a one dim array of one dim arrays! In other words: the difference is more on the surface, not rooted in deep conceptual reasons!

And to be really precise: the Java type system allows you to put down Object[][] so in that sense, it knows that type of Object[][]; but as said, in reality, there are no multi-dimensional arrays; as Java sees that "two dim" thing as an array of references to arrays!

On the other hand: there is a certain notion of "multi dimensional arrays", as for example the JVM specification explicitly mentions:

The first operand of the multianewarray instruction is the run-time constant pool index to the array class type to be created. The second is the number of dimensions of that array type to actually create. The multianewarray instruction can be used to create all the dimensions of the type, as the code for create3DArray shows. Note that the multidimensional array is just an object and so is loaded and returned by an aload_1 and areturn instruction, respectively.

Answer 4

I'm going to go out on a limb here and answer this one, however there is no correct answer for this broad question.

We first have to ask, what makes an array multidimensional?

I'm going to assume that your interviewer considers a multidimensional array one with a fixed size (as you've shown in your question), where it cannot be considered "jagged". According to Microsoft, a jagged array in C# is as follows:

The elements of a jagged array can be of different dimensions and sizes.

In Java, a multidimensional array is simply an array, where each element is also an array. These arrays must be defined with a fixed size in order for elements to be indexed within them, but jagged arrays can be of different sizes, as stated above.

An ArrayList is backed by an array; however, the array expands when a certain number of elements are added to it. For this reason, the ArrayList could become jagged, and could be considered not to be multidimensional any longer.

Edit: After rereading everything over a few times, I'm sure that your interviewer was just trying to confuse you. It honestly doesn't make sense for one data type (an array) to be multidimensional, and another data type (an ArrayList that uses an array) to not be multidimensional.

Answer 5

The interviewer's claim is nonsensical.

One can argue, as you see on this page, that Java does not have true multidimensional arrays, in which case it does not have multidimensional ArrayLists either. On the other hand, it certainly allows you to represent multidimensional structures via arrays and ArrayLists in the same way.

To define a major distinction between the two is fairly arbitrary and pointless.

Possibly the interviewer was just trying to start a technical debate, to test your ability to explain the details.

Answer 6

An ArrayList is an implementation of List. It's a List that is implemented using arrays. The usage of arrays is an implementation detail. The list interface doesn't support the concept of multi-dimensional lists therefore you wouldn't expect ArrayList to either. Further it isn't addressed as a use case of a traditional list data structure.

Arrays support multi-dimensionality because it's a language feature of Java.

Answer 7

Because it isn't dimensional at all. It is an object with an API. Any appearance of multi-dimensionality is provided by its API, but it is purely in the eye of the beholder. An array on the other hand is dimensional, and can therefore be multidimensional too.