Re: Generics, extending LinkedList<T>, and unchecked casts
Mark Maloof <maloof@cs.georgetown.edu> wrote:
I need an ordered sequence, so I extended LinkedList<T>.
Lists are ordered already. You probably mean you need a sorted list.
Since I'm implementing an ordered collection, its elements must implement
Comparable<T>. I came up with the following implementation, which
seems to work, but I cannot figure out how to avoid the unchecked cast
at the end of the insert method:
public class OrderedLinkedList<E> extends LinkedList<E> {
public void insert( Comparable<E> element ) {
int i = 0;
while ( i < size() && element.compareTo( this.get( i ) ) >= 0 ) {
i++;
} // while
// add( i, element ); // compiler error
add( i, (E) element ); // unchecked cast
} // OrderedLinkedList::add
O(n) for insertion. as expected for search in a linked list. You might
prefer a tree if this list is expected to get big. But that's not your
question, so nevermind :)
Your compiler error indicates that you can't insert element, because it's not
type E. It's type Comparable<E>. Your unchecked cast warning indicates
that there is no runtime checking of this, as E is erased by the compiler.
So it will let you do something broken like using a Comparable<E> in a method
that expects an E.
The problem is that you think that Comparable<E> implies the object is type E.
Not so. Say I declare MyClass extends Object implements Comparable<Foo> and
pass it to your OrderedLinkedList<Foo>. It would happily insert the
MyClass into your LinkedList. You'll get a ClassCastException somewhere
down the road when something expects a Foo and you give them a MyClass.
Try
public class SortedLinkedList<E extends Comparable<E>> {
public void insert( E element ) { ...
Which specifies that it can only be used with homogeneous things that are
Comparable to themselves.
--
Mark Rafn dagon@dagon.net <http://www.dagon.net/>