Is it possible to cast an instance of List<ArrayList> to List<List> in O(1) time in Java?

I have an instance of List<ArrayList<Integer>>, how can I change it to type List<List<Integer>> ?

My solution is:

List<ArrayList<Integer>> list1 = new ArrayList<>();

list1.add(new ArrayList<>());
list1.add(new ArrayList<>());

List<List<Integer>> list2 = new ArrayList<>(list1);

However, this method takes time O(n), with n the length of list1.

Question1: Is there better method?

The following naive method is compile error:

List<List<Integer>> list2 = (List<List<Integer>>) list1;

Question2: why is above method compile error?

PS: It’s from a practical problem. I just simplify the production code to above question. In production code, it’s List<SomeList>, the SomeList implements List interface but has some special functions not declared in List. In intermediate process, we require the content must be SomeList since we have to use these special functions. However, in the end we just need to ouput our result to List<List> for other group to use.

Answer

First, an answer to your Question 2: The reason that your naive cast does not work is because it could lead to type errors. Consider for example the following code snippet:

List<ArrayList<String>> list = new ArrayList<>();
List<List<String>> list2 = (List<List<String>>) list; // Wrong cast
list2.add(new LinkedList<>());
list.get(0).ensureCapacity(42); // Oops, LinkedList does not have this method.

As to your Question 1: A type-safe method to do exactly what you want in O(1) does not exist. You could fool the type system using raw types:

List<List<String>> list2 = (List) list;

But this would simply allow the kind of problems described above without the compiler error. But if you’re sure the list will never change afterwards, it may be allowable. Sometimes. But probably you really shouldn’t.

Better would be to change the type of your second list to List<? extends List<String>>. This would effectively prohibit adding elements to the list through the new reference, because the compiler cannot determine the type of List in list2 from its type:

List<ArrayList<String>> list = new ArrayList<>();
List<? extends List<String>> list2 = (List<? extends List<String>>) list;
list2.add(new LinkedList<>()); // Not possible anymore
list2.add(new ArrayList<>()); // Also not possible