在Java中对双链表进行排序

Question

我不得不为我的编程类做一个链表列表程序。它可以工作，每次插入号码时，它都会放在列表的开头。现在我的老师希望我们参加我们的链接列表程序并按升序对数字进行排序。我完全失去了如何做到这一点。任何人都可以将我指向正确的方向吗？ 这里是我的清单代码：

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 ）在最简单的情况下，列表已经排序：

- >甲

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 - 2个新>Ç链接，从A→B和从B→C的另一个链接。

以这种方式插入gaurante确保您的列表保持排序。

具体

因此，您将不得不修改应用程序的插件（..）方法，在列表的beggining启动，并检查各DoubleNode，走，和“记忆”，即存储先前的DoubleNode，直到它到达列表的末尾---或者它看到最后一个节点是新节点的<，并且当前节点>新节点。