Sorting a double Linked List in Java

Question

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

Answer 1

The idea

1) In the simplest case , the list is already sorted :

-> A

2) Now, consider the "next" case (i.e. where you are adding 1 new element to a list of size 1)

-> A [now, i am going to try adding C]

you can simply check if C is > than A, in which case , you add "C" to the end (->A->C)

3) We can generalize case (2) : In any subsequent cases, you will have to walk down the list, until you "see" a new node which is > than the one you are inserting.

-> A -> C [adding B]

check 1: A (B > A)
check 2: C (B < C) ! 

This means that we can replace the links as follows :

replace A -> C with 2 new links, 1 from A -> B , and also another from B -> C.

Inserting in this manner gaurantees that your list remains sorted.

Concretely

You will thus have to modify the insert(..) method of your application, to start at the beggining of the list, and check each DoubleNode, walking down, and "remembering" i.e. storing the previous DoubleNode, until it either reaches the end of the list --- OR it sees that the last node was < than the new node, and the current node is > than the new node.