Inner static class inside inner class cannot be co

Question

Inspired in this question: How to implements Iterable I decided to make a basic linked list implementation and implement an iterator in order to have a code like this:

MyList<String> myList = new MyList<String>();
myList.add("hello");
myList.add("world");
for(String s : myList) {
    System.out.println(s);
}

The code wasn't hard to deal with, creating a class MyList<T> implements Iterable<T> with a private static class Node<T> and a private class MyListIterator<T> implements Iterator<T>, but then I came across a problem when implementing my own version of Iterator#remove:

class MyList<T> implements Iterable<T> {
    private static class Node<T> {
        //basic node implementation...
    }
    private Node<T> head;
    private Node<T> tail;
    //constructor, add methods...
    private class MyListIterator<T> implements Iterator<T> {
        private Node<T> headItr;
        private Node<T> prevItr;
        public MyListIterator(Node<T> headItr) {
            this.headItr = headItr;
        }
        @Override
        public void remove() {
            //line below compiles
            if (head == headItr) {
                //line below compiles
                head = head.getNext();
                //line below doesn't and gives me the message
                //"Type mismatch: cannot convert from another.main.MyList.Node<T> to
                //another.main.MyList.Node<T>"
                head = headItr.getNext();
                //line below doesn't compile, just for testing purposes (it will be deleted)
                head = headItr;
            }
        }
    }
}

This error message raised my curiosity. I was looking on the net about this problem but found nothing (or probably I'm not so good at searching this kind of issues). What would be the reason of two variables from the same type being compared but not being assignable to each other?

By the way, I know that I can just look at the code of LinkedList and check how the Java designers implemented this and copy/paste/adapt it to my own implementation, but I prefer to have an explanation and understanding of the real problem.

Complete code that shows my current implementation of MyList class:

class MyList<T> implements Iterable<T> {
    private static class Node<T> {
        private T data;
        private Node<T> next;
        public Node(T data) {
            super();
            this.data = data;
        }
        public T getData() {
            return data;
        }
        public Node<T> getNext() {
            return next;
        }
        public void setNext(Node<T> next) {
            this.next = next;
        }
    }
    private Node<T> head;
    private Node<T> tail;
    private int size;
    public MyList() {
        head = null;
        tail = null;
    }
    public void add(T data) {
        Node<T> node = new Node<T>(data);
        if (head == null) {
            head = node;
            tail = head;
        } else {
            tail.setNext(node);
            tail = node;
        }
        size++;
    }
    private class MyListIterator<T> implements Iterator<T> {
        private Node<T> headItr;
        private Node<T> prevItr;
        public MyListIterator(Node<T> headItr) {
            this.headItr = headItr;
        }
        @Override
        public boolean hasNext() {
            return (headItr.getNext() != null);
        }

        @Override
        public T next() {
            T data = headItr.getData();
            prevItr = headItr;
            if (hasNext()) {
                headItr = headItr.getNext();
            }
            return data;
        }

        @Override
        public void remove() {
            if (head == headItr) {
                //problem here
                head = headItr.getNext();
            }
            //implementation still under development...
        }
    }
    @Override
    public Iterator<T> iterator() {
        return new MyListIterator<T>(head);
    }
}

Answer 1

The other three are right: you need to change
private class MyListIterator<T> implements Iterator<T>
to
private class MyListIterator implements Iterator<T>
but once you do that, you will also need to change your iterator() method:

public Iterator<T> iterator() {
    return new MyListIterator(head); //was 'return new MyListIterator<T>();'
}

Or else you will get another error. Once you make the second change, then it should work.

Answer 2

The iterator should be declared as

private class MyListIterator implements Iterator<T>

and not as

private class MyListIterator<T> implements Iterator<T>

By declaring it as MyListIterator, its generic type T is not the same T as the T from its enclosing class.

Answer 3

This is the problem:

class MyList<T> implements Iterable<T> {
    private class MyListIterator<T> implements Iterator<T> {
        ...
    }
}

(It doesn't help that in your cut down version you've made MyList non-generic.)

At that point there are two different T type variables - the one in the nested class and the one in the outer class. You don't need Node to be generic - you just need:

class MyList<T> implements Iterable<T> {
    private class MyListIterator implements Iterator<T> {
        ...
    }
}

Now there's only one T - the one in the outer class. It's not like you want the list iterator to have a different T from the one declared in the enclosing instance, so you don't want it to be generic.

To put it another way: try making MyListIterator generic in a type parameter with a different name, and then it'll be clearer what's going wrong, as the two names will be distinguishable in the error message. It's effectively:

Type mismatch: cannot convert from another.main.MyList.Node<TOuter> to
another.main.MyList.Node<TInner>

(or vice versa).

Answer 4

Remove the type parameter from the declaration of MyListIterator:

private class MyListIterator implements Iterator<T>

and the call in iterator()

public Iterator<T> iterator() {
    return new MyListIterator(head);
}

In your current version the T of MyListIterator isn't the same T as the one in MyList.