Java，为LinkedList创建一个插入函数，以升序添加所有插入的元素

Question

我必须为我的Java项目从头开始创建一个链表类，该类将在其适当位置插入一个日期对象。我的排序格式是简单地将年/月/日作为一个字符串，用于比较两个Date对象。我的compareTo函数似乎不是问题的根源，因为简单的selectionSort测试产生了正确的结果。我的插入只是简单地使用第一个元素来与其他所有元素进行比较，这是不正确的。经过一段时间的修补，我不知道如何解决这个问题。

public class Date212 {
    private int month;
    private int day;
    private int year;
    public Date212(String d){
        String temp;
        temp = d.substring(4,6);
        int theMonth = Integer.parseInt(temp);
        temp = d.substring(6,8);
        int theDay = Integer.parseInt(temp);
        temp = d.substring(0,4);
        int theYear = Integer.parseInt(temp);
        setDate212(theYear, theMonth, theDay);
    }
    public void setDate212(int y, int m, int d){
        year = y;
        month = m;
        day = d;

    }
    public int getMonth(){
        return month;
    }
    public int getDay(){
        return day;
    }
    public int getYear(){
        return year;
    }
    public int compareTo(Date212 other){
        if(this.toString().compareTo( ((Date212)other).toString()) < 0)
            return -1; //This temp is smaller
         else if(this.toString().compareTo( ((Date212)other).toString()) > 0){
            return 1; //This temp is bigger
        }
        return 0; //Must be equal
    }
    public String toString(){
        String s = Integer.toString(year) + "/" + Integer.toString(month) + "/" + Integer.toString(day);
        return s;
    }           
}

public class ListNode
{
   protected Date212 data;
   protected ListNode next;
   public ListNode(Date212 d)
   {
      data = d;
      next = null;
   }  // constructor
}  // class ShortNode

public class LinkedList {
/** First node in linked list - dummy node */
private ListNode first = new ListNode(null);
/** Last node in linked list */
private ListNode last = first;
/** Number of data items in the list. */
private int length = 0;
/**
 * Gets the number of data values currently stored in this LinkedList.
 * 
 * @return the number of elements in the list.
 */
public int getLength() {
    return length;
}
/**
 * Appends a String data element to this LinkedList.
 * 
 * @param data
 *            the data element to be appended.
 */
public void append(Date212 d) {
    ListNode n = new ListNode(d);
    last.next = n;
    last = n;
    length++;
} // method append(String)
/**
 * Prepends (adds to the beginning) a String data element to this
 * LinkedList.
 * 
 * @param data
 *            the data element to be prepended.
 */
public void insert(Date212 d) {
    ListNode n = new ListNode(d);
    if (length == 0) //If your list is empty
    {
        last = n;
        first.next = n;
        n.next = null;
        length++;
    }
    else //There is element
    {
        ListNode p = first.next; //Start with the first element
        for(int i = 0; i<length; i++){
            if(p.data.compareTo(d) < 0){ //If you are smaller than the *following* element
                n.next = p.next; //Insert the element after the actual
                p.next = n;
                return; //Return early
            }
            p = p.next;
        }
        //We are greater than any element
        this.append(d);
    }
    }

/**
 * Determines whether this ShortSequenceLinkedList is equal in value to the
 * parameter object. They are equal if the parameter is of class
 * ShortSequenceLinkedList and the two objects contain the same short
 * integer values at each index.
 * 
 * @param other
 *            the object to be compared to this ShortSequenceLinkedList
 * 
 * @return <code>true</code> if the parameter object is a
 *         ShortSequenceLinkedList containing the same numbers at each index
 *         as this ShortSequenceLinkedList, <code>false</code> otherwise.
 */
public boolean equals(Object other) {
    if (other == null || getClass() != other.getClass()
            || length != ((LinkedList) other).length)
        return false;
    ListNode nodeThis = first;
    ListNode nodeOther = ((LinkedList) other).first;
    while (nodeThis != null) {
        // Since the two linked lists are the same length,
        // they should reach null on the same iteration.
        if (nodeThis.data != nodeOther.data)
            return false;
        nodeThis = nodeThis.next;
        nodeOther = nodeOther.next;
    } // while
    return true;
} // method equals
public String printList(){
    String s = "";
    ListNode p = first.next;
    while(p != null){
            s += p.data.toString() + "n";
            p = p.next;
        }
        return s;
}
 }// class LinkedList

Answer 1

您的插入代码扫描到记录为列表长度的节点数。这本身并不一定是错误的，但最好只使用节点的next引用来确定何时到达终点。使用next会更好的一个原因是您的代码不那么脆弱：例如，如果在末尾之前插入节点时，它未能正确管理列表长度，那么插入代码本身仍然可以正常工作。

以下是编写代码的另一种方式：

public void insert(Date212 d) {
    ListNode n = new ListNode(d);
    ListNode p = first;
    // Find the insertion point
    while ((p.next != null) && (p.next.data.compareTo(d) < 0)) {
        p = p.next;
    }
    // Insert the node
    n.next = p.next;
    p.next = n;
    if (n.next == null) {
        last = n;
    }
    // Update the list length
    length++;
}

Answer 2

与其在正确的位置插入元素，我认为在列表上插入元素会更容易，然后像Collections.sort（myList，myComparator）那样对列表进行排序。

Answer 3

在单链表中，插入需要引用要插入元素的节点。因此，我们从p=first开始，遍历列表，直到找到一个p.next，它比要插入的元素大。这意味着我们应该在p之后和p.next之前插入新元素。这是通过对您的代码进行轻微修改来实现的，如下所示

请注意，这是一个按升序排序的列表。对于按降序排序的，如果（p.next.data.compareTo（d）<0）。

else //There is element
    {
        ListNode p = first; //Start with the head, p will point to the element AFTER which insertion should take place
        for(int i = 0; i<length; i++){
            if(p.next.data.compareTo(d) > 0){ //If ele to insert is lesser than next ele
                n.next = p.next; //Insert the element after the actual
                p.next = n;
                length++;
                return; //Return early
            }
            p = p.next;
        }
        //We are greater than any element
        this.append(d);
    }