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!

 

[rezeew]

Hi there,

I can see that you have put in a lot of effort into your code and it's great that you're seeking help when you encounter a problem. Sorting a linked list in Java can be a tricky task, but with some guidance, you will be able to solve it.

Firstly, I would suggest breaking down your code into smaller functions and testing each one individually. This will help you identify where exactly the problem lies. For example, you can create a function to insert a node at the beginning of the linked list, and another function to insert a node at the end. This will make your code more organized and easier to debug.

Secondly, I noticed that in your while loop, you are only checking if the current node's data is less than the data you are trying to insert. However, you also need to check if the current node's data is greater than the data you are trying to insert. This will help you determine the correct position to insert the new node.

Lastly, I would recommend using a temporary variable to keep track of the previous node while traversing through the linked list. This will be helpful when you need to insert the new node in the correct position.

I hope these suggestions help you in solving your problem. Keep up the good work and don't hesitate to seek help when needed. Good luck!