In Java, if I want to make a generic list or binary search tree, do I make Node class extend comparable AND the list or tree class?

Question

I am wondering what is the best way to do this?

class Node<E>{ } 

or

class Node<E extends Comparable<E>>{ }

Then do I need to make the list or bst class extend Comparable as well or can I do the below declaration? Any suggestions will be appreciated.

class BST { private Node<E> root; ... }

or

class BST<E extends Comparable<E>>

I have seen a few variations and would like to know the best one to do. Thanks!!!

Answer 1

I think what you are trying to do is create a new collection. If this is for learning purpose, then you could just define your BST as:

class BST<E implements Comparable<E>>{
  private Node root;
  //...
  private class Node{ // instances of Node are bound to the instance of BST
    E elem;
    Node left, right;
  }
}

or with a static inner class:

class BST<E implements Comparable<E>>{
  private Node<E> root;
  // ...
  private static class Node<X implements Comparable<X>>{
    // similar
  }
}

Note that it's good practice to have your Node class defined as an inner class and make it either private or with a private constructor. This ensures encapsulation of the implementation.

I want to point out that this is not the approach taken in the SDK. In the library, it's always possible to create a data structure by passing an appropriate Comparator<E> so that no natural ordering is required or can be overwritten. If you want to follow this other approach look at the implementation of TreeSet or something like that. You can either pass the Comparator or the type in the collection will be checked at run time to implement Comparable. This has the advantage of being more flexible because you can add to the collection objects for which you cannot change the implementation.

Finally, if you need to implement a collection for a project or work, then don't. The SDK has plenty of collections and there are also the Guava collections.

Answer 2

That's simple.

Have a parent (abstract) class extends Node and implement the Comparable interface like:

public class ComparableNode extends Node implemnt Comparable

Or, have your Node implement Comparable; then have your generic interface like:

private List<ComparableNode> list = new ArrayList<CompraableNode> ();

Answer 3

Try this:

class LinkedList<E extends Comparable<E>>{

    class Node<E>{
        E value;
    }

}