Problems With Sorting A Linked List In Java

[heatengine516]

Homework Statement

Create a SortedLinkedList class which implements the LinkedListInterface.

Remember to use the Comparable class

Basically, I need to implement a sorted linked list that uses generics and uses compareTo to sort objects. I need it to be able to sort names alphabetically. Can't use priorities or indexes.

Homework Equations

n/a

The Attempt at a Solution

My main problem is getting the add() function to work properly. It can sort the head and tail, but it's all the stuff in the middle that is the problem. It won't properly sort anything in the middle between the head and tail. It must be something wrong with my while loop.

Here is my code for the add() function:

public void add(T data ) {

// new node
if (isEmpty()) {
head = new LinkedListNode<T>();
head.data = data;
head.next = tail;
tail = head;
return;
}

if(head.data.compareTo(data) > 0) {
LinkedListNode<T> node = new LinkedListNode<T>();
node.data = data;
node.next = head;
head = node;

return;
}

if(tail.data.compareTo(data) < 0){
tail.next = new LinkedListNode<T>();
tail = tail.next;
tail.data = data;

return;
}



LinkedListNode<T> current = head;
LinkedListNode<T> newNode = new LinkedListNode<T>();
newNode.data = data;
System.out.println(" init: " +data + " < " + current.data);

while (current.data.compareTo(data) < 0 ) {



System.out.println(data + " < " + current.data);

current = current.next;

System.out.println(data + " < " + current.data);
}



newNode.next = current.next;
current.next = newNode;
return;

}

Here is the input:

public static void main(String[] args)
{
SortedLinkedList list = new SortedLinkedList();

list.add("jesse");
list.add("rick");
list.add("anne");
list.add("brad");
list.getList();
System.out.println();
list.add("jaime");
list.getList();
}

and here is the output after running:

run SortedLinkedList
init: brad < anne
brad < anne
brad < jesse

anne
jesse
brad
rick

init: jaime < anne
jaime < anne
jaime < jesse

anne
jesse
jaime
brad
rick

I have honestly been working on this for a week and I don't understand why it's not working. I've followed in class examples for our priority and linked queues and online tutorials that are similar but nothing works. Any help would be appreciated. Thank you.

 

[.Scott]

I believe the problem is with:
newNode.next = current.next;
current.next = newNode;

It needs to be:
newNode.next = current;
lastNode.next = newNode;

Then you need to keep track of lastNode, which sill always be the one that was before "current".

So after:
LinkedListNode<T> current = head;
you will have a:
LinkedListNode<T> lastNode = current;

Then before:
current = current.next;
you will have
lastNode = current;

Good luck. Let me know how it goes.

 

[heatengine516]

Thank you! My add() function is working perfectly now! To think I labored for a week or more trying to find a solution while the fix was so simple. Thank you again.

Do you by any chance have any recommendations for texts/tutorials/resources for further understanding of these data structures?

 

[.Scott]

As far as recommended texts, I really don't have any recommendations. Different people learn in different ways. I've been coding for over 4 decades and I pick up new material by reading sample code.

Best of luck!