Sorted Linked List

[Iamthecheese]

Hello,

I'm having trouble translating an algorithm. I'm not sure I coded bits of this correctly, but I'm certain that I have no idea how to compare an item with a node identifier (cannot apply > operator with T,T) but since this is an insert sorted method rather than insert from back or front some sort of compare (compareTo()?) is necessary to establish a sorting procedure, yes? I guess what I'm asking is the proper syntax for said code. Thanks, any help is appreciated.

package ListPkg;
import ExceptionPkg.InvalidListOperationException;

public class SortedLinkedList <T extends Comparable<T>> extends LinkedList<T>
{
        public SortedLinkedList()
        {
                super();
        }
        public SortedLinkedList(String listName)
        {
                super(listName);
        }
        public void insertAtFront(T item) throws InvalidListOperationException
        {
                throw new InvalidListOperationException("Insert at front of list is not allowed");

        }
        public void insertAtBack(T item) throws InvalidListOperationException
        {
                throw new InvalidListOperationException("Insert at back of list is not allowed");
        }
        public T insertSorted(T item)
        {
                ListNode<T> newNode;
                if(isEmpty())
                {
                //      data = item;
                //      nextNode = null;
                        newNode = new ListNode<T>(item,null);
                        firstNode = lastNode = newNode;
                }
                else
                {
                        ListNode<T> current = firstNode;
                        if(item < firstNode.data)  //here's a problem
                        {
                                super.insertAtFront(item);
                        }
                        else
                        {
                                current = firstNode;
                                boolean found = false;
                                while(current.nextNode != null && found == false)
                                {
                        if(item > current.nextNode) //here's another
                                        {
                                                current = current.nextNode;
                                        }
                                        else
                                        {
                                                found = true;
                                        }
                                }
                                if(found == true)
                                {
                                        item = current.nextNode;
                                }
                                else
                                {
                                        super.insertAtBack(item);
                                }
                        }
                }
        }
}

[kramerd]

I'm not positive about all the intricacies of templates in Java, but I believe since you have <T extends Comparable<T>> in your class declaration, you can assume that the class for item implements the Comparable interface. That means you can call compareTo, which returns an int, which can be compared using > and <.

[Iamthecheese]

I'm not positive about all the intricacies of templates in Java, but I believe since you have <T extends Comparable<T>> in your class declaration, you can assume that the class for item implements the Comparable interface. That means you can call compareTo, which returns an int, which can be compared using > and <.

Thank you for replying!

I tried this earlier, but I don't think that I implemented it correctly.
e.g.

if(item.compareTo() > current.nextNode.compareTo())

[kramerd]

No, that's not right. Look up the documentation of compareTo. Your code will look something like this:

int answer = item.compareTo(current.nextNode);
if (answer < 0)
   // do something
else if (answer > 0)
   // do something
else // answer == 0
   // do something

[Iamthecheese]

OH OK! So basically use a temp for the compareTo. Thanks! I'll fiddle with this :)

[Iamthecheese]

I got this error. I'm assuming the first temp worked.

***********************************************************************************
SortedLinkedList.java:59: compareTo(T) in java.lang.Comparable<T> cannot be applied to (ListPkg.ListNode<T>)
int temp2 = item.compareTo(current.nextNode);
^
SortedLinkedList.java:75: incompatible types
found : ListPkg.ListNode<T>
required: T
item = current.nextNode;
^
2 errors

[kramerd]

Was the first temp item.compareTo(firstNode.data) ?
If so, you probably need .data in the 2nd as well.

int temp2 = item.compareTo(current.nextNode.data);

[Iamthecheese]

Doh! I feel dumb now. That fixed that also. The only error (so far, now) is how to assign item to current.nextNode.

[kramerd]

Remember that item is of the same type as data, not node. So once again, you need .data at the end:

item = current.nextNode.data;

[Iamthecheese]

I tried that, but now it's saying I'm missing a return statement. I'm pretty sure I'm not missing one.

[kramerd]

The type of method insertedItem is T. That means you need to return something at the end of the method. Do you have instructions that tell you what you are supposed to return? If not, I would just return item at the end.

[Iamthecheese]

Scratch that last post, I found out that for some reason I had the return type listed as T which means it was expecting something to return. This fixed it and the file compiles.

[kramerd]

Great. Good luck. I'm going off line now. 'night.