CODEWITHSUNDEEP
javagenerics
pitosalas
pitosalas

Reputation: 10882

Java Generic formal parameters

I am implementing a simple LinkedList class and I want it to use generics. The class declaration is:

public class LinkedList<E> extends AbstractList<E> implements List<E> {

This is a teaching example, so the Abstract parent and the interface are also my own. The problem arises when I realized that to add and maintain sorting, I need a class (E) which is also Comparable. I thought I could limit that to just the methods where it actually makes a difference. But based on the comments below, that may be my basic misunderstanding.

Here's the code:

  public void addSorted(<E extends Comparable<E>> value) {
    if (front == null || value.compareTo(front.word) <= 0) {
      // insert at front of list
      front = new ListNode<E>(value, front);
    } else {
      // insert in middle of list
      ListNode<E> current = front;
      while (current.next != null && current.next.word.compareTo(value) < 0) {
        current = current.next;
      }
      current.next = new ListNode<E>(value, current.next);
    }
  }

It seemed to me that if I never want to call addSorted then why should the particular class be limited to E's that implement Comparable? Or is there a totally different way to do it, with a generic analog to instances?

Upvotes: 0

Views: 482

Answers (1)

Andy Turner
Andy Turner

Reputation: 140484

Consider what happens if you are able to call both add and addSorted on a LinkedList instance:

LinkedList<String> list = new LinkedList<>();
list.add("c"); list.add("a");
list.addSorted("b");

In this case, where do you expect "b" to be inserted into a list ["c", "a"]:

  • It is lexicographically before "c", so it could be inserted at the start, yielding ["b", "c", "a"];
  • It is lexicographically after "a", so it could be inserted at the end, yielding ["c", "a", "b"];

But neither list is really "sorted" afterwards.

To me, the only obvious way to resolve this ambiguity is to force all adds to be done in a sorted way. This implies that you should create a subclass of LinkedList, SortedLinkedList, which overrides the LinkedList.add method:

class SortedLinkedList<E extends Comparable<E>> extends LinkedList<E> {
  void add(E element) {
    // The implementation of addSorted.
  }
}

In general, the way I would handle methods that should only available for certain generic types is to do it using a method which accepts an instance of the class as the first parameter, outside the definition of the class (or inside the definition of the class, but defined as static). This means that it's not part of the interface of the class, so it's not present for classes with incompatible generic types.

For example, if you wanted to add a sort method to sort LinkedLists, this is obviously only sensible for ones with Comparable elements:

static <E extends Comparable<E>> void sort(LinkedList<E> list) {
  // ...
}

For example:

LinkedList<String> strList = new LinkedList<>();
// ... Add elements.
sort(strList); // OK.

LinkedList<Object> objList = new LinkedList<>();
// ... Add elements.
sort(objList); // Compiler error - Object is not a valid bound.

Upvotes: 2

Related Questions