How come Java doesn't accept my LinkedList in a Generic, but accepts its own?

Question

For a class assignment, we can't use any of the languages bultin types, so I'm stuck with my own list. Anyway, here's the situation:

public class CrazyStructure <T extends Comparable<? super T>> {
    MyLinkedList<MyTree<T>> trees; //error: type parameter MyTree is not within its bound
}

However:

public class CrazyStructure <T extends Comparable<? super T>> {
    LinkedList<MyTree<T>> trees;
}

Works. MyTree impleements the Comparable interface, but MyLinkedList doesn't. However, Java's LinkedList doesn't implement it either, according to this. So what's the problem and how do I fix it?

MyLinkedList:

public class MyLinkedList<T extends Comparable<? super T>> {
    private class Node<T> {
        private Node<T> next;
        private T data;

        protected Node();
        protected Node(final T value);
    }

    Node<T> firstNode;

    public MyLinkedList();
    public MyLinkedList(T value);

    //calls node1.value.compareTo(node2.value)
    private int compareElements(final Node<T> node1, final Node<T> node2);

    public void insert(T value);
    public void remove(T value);
}

MyTree:

public class LeftistTree<T extends Comparable<? super T>>
        implements Comparable {

    private class Node<T> {
        private Node<T> left, right;
        private T data;
        private int dist;

        protected Node();
        protected Node(final T value);
    }

    private Node<T> root;

    public LeftistTree();
    public LeftistTree(final T value);
    public Node getRoot();

    //calls node1.value.compareTo(node2.value)
    private int compareElements(final Node node1, final Node node2);

    private Node<T> merge(Node node1, Node node2);
    public void insert(final T value);
    public T extractMin();
    public int compareTo(final Object param);
}

Answer 1

I assume your MyTree is the same as LeftistTree. The problem with the signature is that it doesn't implement Comparable<LeftistTree<? super T>>.

So the signature should be:

public class LeftistTree<T extends Comparable<? super T>>
    implements Comparable<LeftistTree<? super T>>

The reason is that your MyLinkedList is not like a regular LinkedList. A regular LinkedList is of type: LinkedList<T> there are no bounds on T. You require with MyLinkedList that the parameter implement a Comparable of itself (or its superclass), but in fact LeftistTree was implementing a raw Comparable (or Comparable<?>) so the Comparable was not guaranteed to be related to the type.

Answer 2

Why does your linked list must accept a Comparable typed?

For a collection data structure, forcing your collection to only accept specific data type is very limiting. If you would like to have a sorted linked list, it is better to accept any element and allow your linked list to accept a Comparator object. If you do not provide a Comparator, then you can rely on the natural ordering of the contained element if they are of Comparable typed.

Take a look at the SortedSet or SortedMap api signature for some example.