[nweid1]

I have to sort a linked list of doubles in ascending order. I have the code partially working but when I input increasing then decreasing values the list becomes unsorted. For example, it I enter 4, 5, 6, 2, -5, 20, -20 the output is [ -20.0 -5.0 2.0 4.0 5.0 6.0 20.0 ] but if I enter 7 after that the output is [ -20.0 -5.0 2.0 4.0 5.0 6.0 20.0 7.0 ]. So, I know my problem is in the else statement within my insert method but I'm not sure where the mistake is.

Here is the code for the list:

public class SortedList {

	private DoubleNode head = null;
	private int listLength;

	public static void main(String[] args) {
		SortedList list = new SortedList();
		list.insert(4);
		list.insert(5);
		list.insert(6);
		list.insert(2);
		list.insert(-5);
		list.insert(20);
		list.insert(-20);
		list.insert(7);
		list.insert(-29);
		list.insert(23);
		list.insert(-100);
		list.insert(-99);
		list.insert(-101);
		list.insert(10);

		System.out.println(list.toString());
		
	}
	
	public void insert(double value) {

		if(listLength == 0 || value <= head.getData()) {
			head = new DoubleNode(value, head);
			listLength++;
		}
		
		else {
			DoubleNode temp = new DoubleNode(value, null);
			DoubleNode current = head;
			//while the given value is less than the current nodes value, go to the next node
			for (int i = 1; value > current.getData() && current.getLink() != null; i++) {
				current = current.getLink();//set current as the next node
			}
			temp.setLink(current.getLink()); //set temp's link as current's link
			current.setLink(temp);
			listLength++;
		}
		
	}
	
	public String toString() {

		String answer = "[ ";
		for (DoubleNode current = head; current != null; current = current
				.getLink()) {
			answer += current.getData() + " ";
		}
		answer += "]";
		return answer;
	}
	
}

and here is the code for the node:

// File: DoubleNode.java based on the DoubleNode class by Michael Main

/**************************************************************************
* DoubleNode provides a node for a linked list with double data in each node.
*
* @note
*   Lists of nodes can be made of any length, limited only by the amount of
*   free memory in the heap. 
*
* @author Michael Main 
*   shortened by Beth Katz and Stephanie Elzer to be only the basics
*
* @version
*   February 2007
***************************************************************************/
public class DoubleNode
{
   // Invariant of the DoubleNode class:
   //   1. The node's double data is in the instance variable data.
   //   2. For the final node of a list, the link part is null.
   //      Otherwise, the link part is a reference to the next node of the list.
   private double data;
   private DoubleNode link;   
   
   /**
   * Initialize a node with a specified initial data and link to the next
   * node. Note that the initialLink may be the null reference, which 
   * indicates that the new node has nothing after it.
   * @param initialData
   *   the initial data of this new node
   * @param initialLink
   *   a reference to the node after this new node--this reference may be 
   *   null to indicate that there is no node after this new node.
   * @postcondition
   *   This node contains the specified data and link to the next node.
   **/   
   public DoubleNode(double initialData, DoubleNode initialLink)
   {
      data = initialData;
      link = initialLink;
   }
    
   /**
   * Accessor method to get the data from this node.   
   * @param - none
   * @return
   *   the data from this node
   **/
   public double getData( )   
   {
      return data;
   }
    
   /**
   * Accessor method to get a reference to the next node after this node. 
   * @param - none
   * @return
   *   a reference to the node after this node (or the null reference if 
   *   there is nothing after this node)
   **/
   public DoubleNode getLink( )
   {
      return link;                                               
   } 
   
   /**
   * Modification method to set the data in this node.   
   * @param newData
   *   the new data to place in this node
   * @postcondition
   *   The data of this node has been set to newData.
   **/
   public void setData(double newData)   
   {
      data = newData;
   }                                                               
    
   /**
   * Modification method to set the link to the next node after this node.
   * @param newLink
   *   a reference to the node that should appear after this node in the 
   *   linked list (or the null reference if there is no node after this node)
   * @postcondition
   *   The link to the node after this node has been set to newLink. Any other 
   *   node (that used to be in this link) is no longer connected to this node.
   **/
   public void setLink(DoubleNode newLink)
   {                    
      link = newLink;
   }  
}
           

Thanks

[blackcompe]

If you try a few more inputs that are more mixed, you'll probably see unsorted elements earlier in the resultant list. I think the problem is with your for loop.

Suppose the elements to be inserted are 4, 5, 6, 2, -5, 20, -20, and 7. When you input the first 7 numbers everything is OK and you get: [ -20.0 -5.0 2.0 4.0 5.0 6.0 20.0 ].

DoubleNode current = head;
for (int i = 1; value > current.getData() && current.getLink() != null; i++) {
     current = current.getLink();//set current as the next node
}

In the loop, when current points to sixth number, 6.0, the loop condition says is 7.0 > 6.0. That's true, so current now points to 20.0, and the loop condition becomes 7.0 > 20.0. That's false, and you break out the loop with current pointing to 20.0. Then after the loop you attach the new node with 7.0 to the tail of the node with 20.0.

temp.setLink(current.getLink()); //set temp's link as current's link
current.setLink(temp);

An easy fix would be to keep a pointer to the previous node.

Node curr = head, prev;
while(curr != null && curr.val < myVal) { //breaks when bigger value is found
     curr = curr.next;
     prev = curr;
}

//you want to insert between prev and curr
Node newNd = new Node(myVal);
newNd.next = curr;
prev.next = newNd;

This post has been edited by blackcompe: 21 March 2012 - 06:23 PM

[nweid1]

I get what you're saying but I don't really follow your code. Sorry lol I'm new to this stuff

[Crowz]

I'm not a great programmer, but here's my two cents...
Your code is awkward... Why not make methods like this:

insert(AnyType data)
remove(AnyType data)
find(AnyType data)
swap(TreeNode n, TreeNode m)
sort()

insert would be like

TreeNode newNode = new TreeNode (data, null)
tail.next=newNode

find would be like

TreeNode current=header
while(current!=null)
if(current.data==data){
   return current.data;
} else {
   current=current.next;

Swap would just change the pointers and I'm too lazy to write out how

sort would be like

TreeNode current=header;
while(current!=null) {
if(current.data.compareTo(n.data)>0) {
swap(n,current);
current=current.next;
}else if(current.data.compareTo(n.data)<0) {
swap(current,n);
current=current.next;
}else{
current=current.next;
}
}

Then you add a loop and a boolean to see if things were swapped... I guess this is comparable to bubble sort? That may be N^2 run time, but hey, it's easier than writing
Well, that's butchered code but there's what I would do. Not sure if it helps you.

This post has been edited by Crowz: 21 March 2012 - 08:16 PM

[macosxnerd101]

Bubblesort is a horrendous sorting algorithm to begin with, though simple with arrays. It gets easier to mess things up with Linked Lists. Mergesort and Insertion Sort are the most efficient sorting algorithms for Linked Lists, as they focus on Node insertion rather than swapping. Take a look at using one of them to simplify your life. Insertion Sort will be easier to implement.