Making a Linked list using Generics

Question

Hello.

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.

Answer 1

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);

Answer 2

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).

Answer 3

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);
}

Answer 4

• A generic list would look like this:

  List<Creature> list = new LinkedList<Creature>();
  

• In order to sort them using Collections.sort(..) you have to make Creature implement Comparable<Creature>

Read this for more info on "that generic stuff"

If you are to define your own generic class, this is the following way:

public class LinkedList<E> {
   public void add(E element) {..}
   public E get(int idx) {..}
}

Answer 5

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.