Problems With Sorting A Linked List In Java

In summary, the conversation was about creating a SortedLinkedList class that implements the LinkedListInterface and uses the Comparable class to sort objects alphabetically. The main issue was with the add() function, which was not properly sorting items in the middle of the list. The solution was to keep track of the lastNode and update it accordingly. The person also asked for recommendations for further understanding of data structures, to which the expert did not have any specific recommendations but suggested reading sample code.
  • #1
heatengine516
Gold Member
225
18

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.
 
Physics news on Phys.org
  • #2
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.
 
  • #3
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?
 
  • #4
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!
 
  • #5




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!
 

1) What is a linked list and why is it used in Java?

A linked list is a data structure in Java that consists of a sequence of nodes, where each node contains a data element and a reference to the next node in the list. It is used in Java because it allows for efficient insertion and deletion of elements, as well as dynamic memory allocation.

2) Why is sorting a linked list in Java a challenge?

Sorting a linked list in Java can be challenging because unlike arrays, linked lists do not have an index. This means that accessing and manipulating specific elements in a linked list is more complex, and traditional sorting algorithms may not work as efficiently.

3) What is the most common method used to sort a linked list in Java?

The most common method used to sort a linked list in Java is the merge sort algorithm. This algorithm takes advantage of the linked list's structure and uses a divide and conquer approach to efficiently sort the list.

4) What are some potential issues with sorting a linked list in Java?

One potential issue with sorting a linked list in Java is that it may require extra space and time complexity due to the need to create new nodes and reorganize the list. Additionally, if the list is not properly implemented or if there are duplicate values, the sorting process may not work correctly.

5) How can these problems with sorting a linked list in Java be addressed?

To address these problems, it is important to properly implement the linked list data structure and choose an efficient sorting algorithm. Additionally, handling duplicate values and carefully considering the time and space complexity of the algorithm can help improve the efficiency of sorting a linked list in Java.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
3K
  • Programming and Computer Science
Replies
9
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
11
Views
11K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
10
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
6
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
6K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
1K
Back
Top