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

Question

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

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