Generics collection implementation java compilation error

Question

EDIT :

public class LinkedList<E> {
    private class Node {
        protected Node next, prev;
        protected E data;

        protected Node(E dat) {
            data = dat;
            next = prev = null;
        }
    }

    private Node head, tail;

    public LinkedList() {
        (head = new Node(null)).next = tail = new Node(null);
        tail.prev = head;
        tail.next = head.prev = null;

    }

    public class LinkedListIterator {
        private Node current = null;

        public synchronized void resetToHead() {
            current = head.next;
        }

        public synchronized void resetToTail() {
            current = tail.prev;
        }

        public synchronized E get() {
            if (current!=null) return current.data;
            return null;
        }
    }
}

the problem is that i get the following compilation Error on the emphasized lines :

> Type mismatch: cannot convert from LinkedList<E>.Node<E> to
> LinkedList<E>.Node<E>

what does it mean? and how do i fix this?

btw, the code is only part of the implementation so dont try to logicly figure it out.

Answer 1

--- Edited as the question changes slightly ---

The question is now becoming, how do I have two inner classes coordinate generic types? In short, they don't have to if they are both inner classes of an outer class where the generic type is bound. So even with the public synchronized E get() in the non-generic LinkedListIterator you are returning an E (and it is type safe).

However, if you then reach out to implement java.util.Iterator<E> things fall apart, because that E is based on a different class (interface) so the E has different scoping. How do you fix this? You need to parameterize your Node classes to Node<E> to satisfy that E bindings exist on the implementation of Iterator even when that implementation is being used outside of the scope of it's originating class. This forces Node<E> to be defined statically.

The reason it forces the static definition of Node<E> has to do with garbage collection. An Iterator might still be holding references to Nodes even though the LinkedList is scheduled for garbage collection. Sure, you might be able to keep such a thing from happening with a specific implementation, but the JVM has to allow any implementation (even an errant one).

Perhaps it is easier to explain with code

  public LinkedList<E> {

    public Iterator<E> iterator() {
      return new LinkedIterator(head);
    }

    // private because we don't want instances created outside of this LinkedList
    private class LinkedIterator implements Iterator<E> {

      // Right here, needing a parameterized next node will force Node to be static
      // static inner classes can exist outside of the scope of their parent
      // Since it can exist outside of the parent's scope, it needs it's own generic parameter
      private Node<E> next;

      LinkedIterator(Node start) {
        next = start;
      }

      public boolean hasNext() {
        return next != null;
      }

      public E next() {
        Node<E> retValue = next;
        if (retValue != null) {
          next = retValue.next;
        }
        return retValue;
      }

    }

    // must be static because LinkedList might be garbage collected when
    // an Iterator still holds the node.
    // This E is not the same E as in LinkedList, because it is a E declaration (hiding the above E)
    private static Node<E> {
      Node<E> next;
      Node<E> prev;
      E data;
    }

  }

If you are not careful, you can now wind up back where you started; however, the key is to construct new Node<E> objects when needed in the parent scope. Since that is the same scope where you construct LinkedIterator types, the generic type safety will be ensured.

--- Original post follows ----

By specifying that your node class definition is a Node<E>, you basically create a second, independently scoped generic type E which will hide the outer generic type E in the LinkedList class.

Since none of your classes are static, they will only exist within context of a LinkedList class, which will provide the generics binding. That means you can simplify Node<E> to Node yet still put E class types within the Node class. Same goes for the LinkedListIterator, except that if you want it to implement Iterator you should indicate it implements Iterator<E>.

Due to request, what follows is the code that compiles on my machine, (java 1.6.0_20)

public class LinkedList<E> {

    private class Node {
        protected Node next, prev;
        protected E data;

        protected Node(E dat) {
            data = dat;
            next = prev = null;
        }
    }

    private Node head, tail;

    public LinkedList() {
        (head = new Node(null)).next = tail = new Node(null);
        tail.prev = head;
        tail.next = head.prev = null;

    }

    public class LinkedListIterator {
        private Node current = null;
        public synchronized void resetToHead() {
            current = head.next;
        }

        public synchronized void resetToTail() {
            current = tail.prev;
        }
    }
}

Answer 2

It doesn't understand that the <E> in LinkedListIterator is the same <E> as the parent class. Just remove from the inner class:

    public class LinkedListIterator {
        private Node<E> current = null;

        public synchronized void resetToHead() {
            current = head.next;
        }

        public synchronized void resetToTail() {
            current = tail.prev;
        }
    }

Answer 3

You overdid it a bit by parametrising the embedded classes. I removed all unnecessary ones.

public class LinkedList<E> {
    private class Node {
        protected Node next, prev;
        protected E data;

        protected Node(E dat) {
            data = dat;
            next = prev = null;
        }
    }

    private Node head, tail;

    public LinkedList() {
        (head = new Node(null)).next = tail = new Node(null);
        tail.prev = head;
        tail.next = head.prev = null;

    }

    public class LinkedListIterator {
        private Node current = null;

        public synchronized void resetToHead() {
        current = head.next;
        }

        public synchronized void resetToTail() {
            current = tail.prev;
        }
    }
}

---

Alternatively with a static class Node.

public class LinkedList<E> {
    private static class Node<E2> {
        protected Node next, prev;
        protected E2 data;

        protected Node(E2 dat) {
            data = dat;
            next = prev = null;
        }
    }

    private Node<E> head, tail;

    public LinkedList() {
        (head = new Node(null)).next = tail = new Node(null);
        tail.prev = head;
        tail.next = head.prev = null;

    }

    public class LinkedListIterator {
        private Node<E> current = null;

        public synchronized void resetToHead() {
            current = head.next;
        }

        public synchronized void resetToTail() {
            current = tail.prev;
        }
    }
}