Making a Linked list using Generics

I am currently working hard at a long overdue assignment. I am supposed to make a linked list using generics. Or, I have an interface called Creature that the list is supposed to sort. But how? How can the list sort creatures when the interface cant have a Creature nextCreature pointer? I know of to make a linked list using normal objects, but this generic stuff has me stumped.

This is only a very small part of the task, but I am getting nowhere开发者_开发知识库 because of this.

A generic linked list class usually is implemented using a generic helper class to represent a node of the list. This Node class would contain an element of type T (where T is the generic parameter) and a reference to the next node (of type Node<T>). So it would look like this:

class Node<T> {
    T element;
    Node<T> next;
};

In case of a doubly linked list, the node would also contain a reference to the previous node. Using this Node class, you should be able to define your linked list implementation just fine (the list would simply contain a reference to the first node (and to the last node for doubly linked lists) and then define the list operations by operating on the nodes).

Your problem is you are stuck thinking each object in a linked list has to point to the next (and possibly previous) object. That is not quite right. What you need to do is build a linked list of objects that just hold other objects. So instead of trying to figure out how to modify the Creature so it has pointers, just make a linked list of generic ListEntry objects, each of which has reference(s) to other ListEntrys and can aslo hold some to-be-specified (generic) type T. From the outside it will act like each Creature has reference(s) to others, but from the inside you will know each Creature is just being carried by a ListEntry object. That's one of the things they mean when they talk about encapsulation.

Incidentally, this is how it is done in the Java Collections framework.

Sorting is handled automatically as long as you implement Comparable:

class Creature implements Comparable {
    public int compareTo(Object o) {
        return 0; // TODO: Your compare function here.
    }
}

class Ape extends Creature {}
class Elephant extends Creature {}

Then, you can create a generic list and sort it as such:

public static void main(String[] args) {
    LinkedList<Creature> creatures = new LinkedList<Creature>();
    Collections.addAll(creatures, new Elephant(), new Ape());
    Collections.sort(creatures);
}

public interface Creature {
    public void doSomething();
}

public class MyCreature implements Creature {
    public void doSomething() { }
}

and you use it in your code like this:

List<Creature> genericList = new LinkedList<Creature>();
genericList.add(new MyCreature());
Creature c = genericList.get(0);