List<Integer> cannot be converted to ArrayList<Integer>

Question

At the beginning of my code, there is:

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

And then, (here is to reverse a sub-list):

List<Integer> sub = new ArrayList();
re = reverse(result.get(j)); // error occurs here

There is this method:

public ArrayList<Integer> reverse(ArrayList<Integer> list) {
    List<Integer> newList = new ArrayList<>();

    for(int i=list.size()-1; i>=0; i--) {
        newList.add(list.get(i));}
        return newList;
    }
}

The error message is:

List cannot be converted to ArrayList

Why?

Answer 1

Think of it like this, you have a Fruit called re (I use this name because it's the name of the variable you are using).

Fruit re;

You have a method reverse whose input type is Apple.

public Apple reverse(Apple a) {
    // ...
}

We have a variable re that we declared as Fruit which means we're saying it's always going to be some kind of Fruit, perhaps Apple, but maybe Orange -- or even Banana.

When you try to give the Fruit to the method taking Apple the compiler stops you, because it can't be certain that it's 100% an Apple. For example...

Fruit re = new Orange();
reverse(re);

Yikes! We are putting a square peg into a round hole so to speak. reverse takes Apple, not Orange. Bad things could happen!

Side note: Why is it okay then to assign Apple to something declared as Fruit then? (reverse returns an Apple, Fruit f = reverse(re); is legal.) Because an Apple is a Fruit. If it were declared as the more specific Apple and the return type were the more general Fruit, then there would be an issue here. (If reverse returned Fruit, Apple a = reverse(re); would be illegal.)

If you didn't follow the metaphor, replace Fruit with List and Apple with ArrayList and read the above again. List is Fruit, a general way to describe an abstract idea. ArrayList is Apple, a specific implementation of the abstract idea. (LinkedList could be Orange too.)

In general you want to declare things as the most general thing you can to get the functionality you need. Making the below change should fix your problem.

public List<Integer> reverse(List<Integer> list) {

We are taking some kind of List of Integers and returning some kind of List of Integers.

Answer 2

You're using a specific implementation of the List interface as a return type for the reverse function (namely ArrayList). This forces what you return to be an ArrayList, but you're defining it as List.

To understand, try and change the construction part to use a LinkedList, which also implements List:

List<Integer> newList = new LinkedList<Integer>();

This construction is valid, but now we try and return a LinkedList from a function that returns an ArrayList. This makes no sense since they aren't related (But notice this: they both implement List).

So now you have two options:

Make the implementation more specific by forcing use of ArrayLists:

ArrayList<Integer> newList = new ArrayList<>();

Or better, make the implementation more general by changing the function's return type (any List can be plugged in):

public List<Integer> reverse(List<Integer> list){