在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，直到它到達列表的末尾---或者它看到最後一個節點是新節點的<，並且當前節點>新節點。