Generic Iterator implementation in java

Question

I have the following design: I have an Abstract class Instance, I have a class Library that extends Instance and I have a class File that also extends Instance

I've created my own linked list implementation and it's defined as follows:

public class List<T extends Instance> implements Iterable {
    //some other code here

     public Iterator iterator(){
         return new ListIterator(this);

}

now I've created a class

public class ListIterator<T extends Instance> implements Iterator<T> {
    private List thisList;
    private Node current;

    public ListIterator(List l){
        thisList=l;
        current=thisList.head.next;
    }
    @Override
    public boolean hasNext() {
        if(current==null)
            return false;
        return false;
    }

    @Override
    public T next() {
        Node temp=current;
        current=current.next;
        return temp.data;
    }
}

Where Node is

public class Node<T extends Instance> {
    public Node<T> next;
    public Node<T> prev;
    public T data;

    public Node(T data,Node prev, Node next){
        this.data=data;
        this.prev=prev;
        this.next=next;
    }   
}

so my problem is as follows: the line return temp.data rises an error:

Type mismatch - cannot convert from Instance to T.

What is wrong with this code?

Solution 1

I'd say that Node.data is a reference to an Instance object? If that is the case, the compiler can't automatically change an Instance to a T, because even though T is an Instance object (T extends Instance), any given Instance might not be a T.

The Java Generics tutorial explains it: http://docs.oracle.com/javase/tutorial/extra/generics/subtype.html

Also, in your List<T> class, you should be specifying Iterator and ListIterator as generic using Iterator<T> and ListIterator<T>, or else the compiler won't be able to handle the generics properly. Your Node reference also needs to be generic: Node<T>

Hence you should be using

private Node<T> current;

and

public T next() {
    Node<T> temp=current;
    current=current.next;
    return temp.data;
}

The compiler will usually warn you when you're using a raw type for a generic class.

Solution 2

Did no one notice the bug:

public boolean hasNext() {
    if(current==null)
        return false;
    return false;
}

This is an invariant. Unless I am missing something, the iterator will very quickly return 0 elements!

Comments

[Andrew Spencer]

It'll be easier to figure out what's happening if you post the code of the Node class. Also... this isn't... homework, is it?

[Andrew Spencer]

Because (1) if it's not for homework (or at least, private study) then it's probably a bad idea to implement List yourself, and (2) if it were for homework then we should be helping you to learn from the error, rather than giving you the answer in a can.

[Andrew Spencer]

Btw if you're using an IDE like Eclipse, IntelliJ etc, turn on the option to warn you when you're using raw types instead of generics. It'll give you an extra pointer with this kind of problem. (Though if you get heavily into generics, you'll also come across some warnings you can't get rid of. Generics are a pain.)

[Andrew Spencer]

One more tip - then I'll stop bugging you - read Josh Bloch's Effective Java, which contains an item explaining (far more eloquently than I could) why you shouldn't be writing your own List - except as a learning exercise, of course. Josh Bloch, by the way, was one of the engineers who wrote Java's Collections API.

[mary]

Node.data is of type T and T extends Instance

[Gnat]

I've updated my answer: you will need to specify Node as Node<T> or else it will be treated as untyped (and hence is of type Instance, not T)

[Andrew Spencer]

I think that's the answer the OP wanted. Mine was just wilfully literal-minded.