Сортировка двойного связанного списка в Java

Question

Мне нужно было создать программу Linked 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;
}

}

и вот мой код для узла, данный моим учителем:

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

Идея

1) В простейшем случае список уже отсортирован:

-> A

2) Теперь рассмотрим «следующий» случай (то есть, когда вы добавляете 1 новый элемент в список размером 1)

-> A [сейчас, я собираюсь попробовать добавить C]

Вы можете просто проверить, является ли C> A, и в этом случае вы добавляете "C" в конец (-> A-> C)

3) Мы можем обобщить случай (2): в любых последующих случаях вам придется идти по списку, пока вы не «увидите» новый узел, который> больше, чем тот, который вы вставляете.

-> A -> C [добавление B]

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

Это означает, что мы можем заменить ссылки следующим образом:

заменить A -> C на 2 новых ссылки, 1 из A -> B, а также еще одну из B -> C.

Вставляя таким образом гарантии, что ваш список остается отсортированным.

* 1035 конкретно *

Таким образом, вам придется изменить метод insert (..) вашего приложения, чтобы он начинался с начала списка, и проверять каждый DoubleNode, переходя вниз и «запоминая», т.е. сохраняя предыдущий DoubleNode, пока он либо достигает конца списка --- ИЛИ он видит, что последний узел был <чем новый узел, а текущий узел> чем новый узел.