How to use Comparable as a Generic parameter in a Class

Question

I have a home work in a data structures course, the question is:

---

Implementation of doubly-linked list class.

the methods:

• display()

• length() or size()

• insertSorted(Comparable)

• insertToEnd(Comparable)

• insertToHead(Comparable)

• delete(Comparable)

• boolean search(Comparable)

You must do this in JAVA

Create an application layer to test your class and its methods. Compress all of your source files into a file and rename it as CS214HW1_first_lastName.zip Put your name in the filename. If needed, add a ReadMe.txt file for extra information such as compilation.

---

I implemented everything correctly and the code is working fine, but I used for example: insertSorted(int) instead of insertSorted(Comparable), because I didn't know how to do it.

I searched online, and read the JAVA documentation for (Comparable) but it is not enough :(

Can anybody help, please it is very important?

Here's some of my code, I can't write it all, cuz I don't want my friends to get the same code.

I will take zero if there is same code.

---

Code:

class DLL {    
    class Node {
        Node next;
        Node prev;
        int data;

        Node() {
            next = null;
            prev = null;
            data = 0;
        }

        Node(int dt) {
            next = null;
            prev = null;
            data = dt;
        }
    }

    Node head;

    void insertToHead(int dt) {    
        if (head == null) {    
            head = new Node(dt);    
        }    
        else {
            head.prev = new Node(dt);
            head.prev.next = head;
            head = head.prev;
        }
    }

    public static void main(String args[]) {    
        DLL dll = new DLL();

        dll.insertToHead(1);
        dll.insertToHead(2);
        dll.insertToHead(3);
    }
}

---

Please, somebody, tell me what to change in the beginning of the class.

1. are we gone use extends or implements Comparable<E> or what!

2. and what changes should i do the method insertToHead(Comparable)

3. what changes should i do to the main.

Answer 1

You would probably like to look into how generics work as well. The basic idea is that you would like to set up your class so that it will not know exactly the specific type of object but can be given some hint at the types of things it can expect of a declared generic type.

In your case, you would like to set up your list so that you can create linked lists of anything that can be compared. Java has a class for that which you have mention called Comparable<E> this tells Java that it will be able to call such methods as compareTo on the provided object.

More specifically to your closing questions:

1. Use the following style of class declaration MyClass<MyGenericType extends Comparable<MyGenericType>>. In your case DLL<E extends Comparable<E>>.

2. Switch the method arguments to accept E our declared generic type.

3. You should use the class Integer instead of the primitive type int, and change the creation of your list to DLL<Integer> dll = new DLL<Integer>().

Fully updated version of provided code:

public class DLL<E extends Comparable<E>> {
    class Node {
        Node next;
        Node prev;
        E data;

        Node() {
            next = null;
            prev = null;
            data = null;
        }

        Node(E dt) {
            next = null;
            prev = null;
            data = dt;
        }
    }

    Node head;

    void insertToHead(E dt) {
        if (head == null) {    
            head = new Node(dt);
        }    
        else {
            head.prev = new Node(dt);
            head.prev.next = head;
            head = head.prev;
        }
    }

    public static void main(String args[]) {    
        DLL<Integer> dll = new DLL<Integer>();

        dll.insertToHead(1);
        dll.insertToHead(2);
        dll.insertToHead(3);
    }
}

This new implementation should provide a hint for how to proceed with some of the other homework tasks. For instance you can now compare objects just by their compareTo method which might useful for sorting hint hint.

That doc page gives a very good explanation for how to use this method. You should note that in their docs, they use a generic type called T instead of E, it really doesnt make a difference you can call it whatever you want provided it is unique to your program.

Edit:

An each hint in the sorting direction:

Ojbects which extend the Comparable class have a method which is called compareTo this method is set up so you can call:

object1.compareTo(object2);

this method returns an int which will be:

• > 0 when object1 is greater than object2
• = 0 when object1 is equal to object2
• < 0 when object1 is less than object2

I don't want to give away too much as this is a homework assignment but here is my hint:

The way the above code sets up your classes, you would be able to tell the relationship between NodeA and NodeB by calling:

NodeA.data.compareTo(NodeB.data)

this will return an integer which gives your information according to the list above.

The <=,>=,== operators are likely found in the Integer class's compareTo method.

Something like:

public int compareTo(Object o) {
    int otherNumber = ((Integer) o).intValue();
    int thisNumber = this.intValue();
    if (otherNumber > thisNumber) {
        return 1;
    } else if (otherNumber < thisNumber) {
        return -1;
    } else {
        return 0;
    }
}

but more likely they just do something like:

public int compareTo(Object o) {
    return this.intValue() - o.intValue(); // possibly normalized to 1, -1, 0
}

See the Docs on Integer for more info on this.