Sorting a Linked List

[nweid1]

I had to make a Linked List program for my programming class. It works and every time a number is inserted it is put at the beginning of the list. Now my teacher wants us to take our Linked List program and sort the numbers in ascending order. I am totally lost on how to do this. Can anyone point me in the right direction?
Here is my 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(6);
		list.insert(7);
		
		System.out.println(list.toString());
		
	}
	
	public void insert(double value) {

		head = new DoubleNode(value, head);
		listLength++;
		
	}
	
	public String toString() {

		String answer = "[ ";
		for (DoubleNode current = head; current != null; current = current
				.getLink()) {
			answer += current.getData() + " ";
		}
		answer += "]";
		return answer;
	}
	
	public int find(double value) {
		if (listLength == 0)
			return -1;
		
		int pos = 1;
		for (DoubleNode current = head; current != null; current = current.getLink()) {
			if (current.getData() == value)
				return pos;
			pos++;
		}
		return -1;
	}

	public int size() {
		return listLength;
	}

	public boolean removeAt(int index) {
		if (index < 1 || index > listLength)
			return false;
		
		if (index == 1) {
			if (head != null) {
				head = head.getLink();
				listLength--;
			}
			return true;
		}
		
		DoubleNode current = head;
		for (int i = 1; i < (index - 1); i++) {
			if (current.getLink() == null)
				return false;
			current = current.getLink();
		}
		current.setLink(current.getLink().getLink());
		listLength--;
		return true;
	}

	
}

and here is my code for the node given by my teacher:

// 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;
   }  
}

[Norm]

Are the numbers to be inserted in sorted order
or do you want to sort an existing list (after is has been created)?

[Norm]

Cross posted at Sorting a Linked List

[DarrylBurke]

Another cross post
homework - Sorting a double Linked List in Java - Stack Overflow

db