Generics, extending LinkedList<T>, and unchecked casts

[Mark Maloof]

I need an ordered sequence, so I extended LinkedList<T>. 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

public static void main ( String args[] ) {
OrderedLinkedList<String> oll = new OrderedLinkedList<String>();
oll.insert("cat");
oll.insert("pig");
oll.insert("dog");
oll.insert("hog");
System.out.println( oll );
} // OrderedLinkedList::main

} // OrderedLinkedList class

I'm familiar with Bracha's tutorial and Langer's FAQ, and I've spent a
fair amount of time pounding Google, but I haven't found anything that
deals with this particular issue. (Pointers would be appreciated.) My
intuition tells me that I need to indicate somehow that E extends
Comparable (since LinkedList.add takes an E), but I haven't figured out
how to write something that compiles. Any help would be appreciated.

Mark

 

[Daniel Dyer]

I need an ordered sequence, so I extended LinkedList<T>. 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

public static void main ( String args[] ) {
OrderedLinkedList<String> oll = new OrderedLinkedList<String>();
oll.insert("cat");
oll.insert("pig");
oll.insert("dog");
oll.insert("hog");
System.out.println( oll );
} // OrderedLinkedList::main

} // OrderedLinkedList class

A class that implements Comparable<E> is not itself necessarily assignable
to references of type E, it just means it can be compared with instances
of E.

If you don't need duplicates you could just use a SortedSet. If you do
need to deal with duplicates, you could try this:

public class SortedList<E extends Comparable<E>> extends LinkedList<E>

This means you can only use the list with types that are comparable to
themselves.

The other option you have is to follow the TreeSet way of doing things and
drop the requirement for Comparable and allow a Comparator to be specified.

Also, OrderedList is a bad name, lists are, by definition, ordered.
SortedList might be a better name, at least it will be consistent with
java.util.SortedSet then.

Dan.

 

[Doug Pardee]

public class OrderedLinkedList<E> extends LinkedList<E> {

public void insert( Comparable<E> element ) {

// add( i, element ); // compiler error

I'm not surprised that the compiler is annoyed. Just because something

I need an ordered sequence, so I extended LinkedList<T>. Since I'm
implementing an ordered collection, its elements must implement
Comparable<T>.
[snip]
My intuition tells me that I need to indicate somehow that E extends
Comparable (since LinkedList.add takes an E), but I haven't figured out
how to write something that compiles.

Your intuition was correct. I think that what you wanted was:

public class OrderedLinkedList<E extends Comparable<E>>
extends LinkedList<E> {
public void insert( E element ) {

 

[Mark Rafn]

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 Maloof]

Thanks guys. That worked. I could have sworn that I tried what you
suggested, but apparently not.

Mm.

 

[Daniel Pitts]

Thanks guys. That worked. I could have sworn that I tried what you
suggested, but apparently not.

Mm.

A further suggestion...

Don't extends LinkedList<E>, use an existing implementation of
SortedSet<E> or SortedMap<K, V>

 

[jflanglois]

public class SortedList<E extends Comparable<E>> extends LinkedList<E>
is not quite enough. Take the following for example:

public class Foo implements Comparable< Foo > {
public int compareTo( final Foo foo ) { ... }
}

public class Bar extends Foo { ... }

Now, SortedList< Foo > will work, but SortedList< Bar > will not
because it is Comparable< Foo >, and the constraint requires an object
to be comparable to itself only. Therefore, we need a "wider" bound:

public class SortedList< E extends Comparable< ? super E > > { ... }

At this point, both Foo and Bar will work, because the constraint
allows an object to compare itself to itself or any of its
superclasses.


That said, I agree on doing it the TreeSort way for a more general
approach. I don't know of a way to enforce the constraint that E is
either Comparable or that there exists a Comparator for it, though
(TreeSort seems to simply throw on add).


jfl.

I need an ordered sequence, so I extended LinkedList<T>. 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

public static void main ( String args[] ) {
OrderedLinkedList<String> oll = new OrderedLinkedList<String>();
oll.insert("cat");
oll.insert("pig");
oll.insert("dog");
oll.insert("hog");
System.out.println( oll );
} // OrderedLinkedList::main

} // OrderedLinkedList class

A class that implements Comparable<E> is not itself necessarily assignable
to references of type E, it just means it can be compared with instances
of E.

If you don't need duplicates you could just use a SortedSet. If you do
need to deal with duplicates, you could try this:

public class SortedList<E extends Comparable<E>> extends LinkedList<E>

This means you can only use the list with types that are comparable to
themselves.

The other option you have is to follow the TreeSet way of doing things and
drop the requirement for Comparable and allow a Comparator to be specified.

Also, OrderedList is a bad name, lists are, by definition, ordered.
SortedList might be a better name, at least it will be consistent with
java.util.SortedSet then.

Dan.