在節點之間添加元素Ordered LinkedList

Question

我查詢了本網站上的搜索引擎，但沒有看到任何與我正在尋找的內容相匹配的內容，所以我希望此問題尚未在其他地方得到解答。我正在嘗試完善我的有序鏈接列表的添加方法。程序的其餘部分運行良好，並且按照測試工具中指定的列表打印列表，我希望對這些名稱進行排序。

我的輸出是這後幾個電話添加和線束刪除：

Sue, Bill, Michael, Someguy, Michael, Carl, Steve, Carl, Sue 
Sue, Bill, Someguy, Michael, Steve, Carl, Sue 
Sue, Bill, Someguy, Michael, Steve, Carl, Sue, Sue, Bill 

我想是這樣的： 蘇，蘇，比爾，邁克爾，邁克爾，卡爾，卡爾，史蒂夫，等...

我的加入方法：

public boolean add(Comparable obj) 
{ 
    OrderedListNode newNode = new OrderedListNode(obj, null, null); 
    if(tail == null) { 
    tail = newNode; 
    head = tail; 
    modCount++; 
    return true; 

    } 
    if(((Comparable)(head.theItem)).equals(obj)){ 
     tail.previous = newNode; 
     modCount++; 
     return true; 
    }else{ 


    tail.previous.next = newNode; 
    newNode.previous = tail.previous; 
    newNode.next = tail; 
    tail.previous = newNode; 
    modCount++; 
    return true; 
    } 
} 

整個代碼，因爲它要求：

package dataStructures; 


public class OrderedLinkedList 
{ 

/************************************************************************** 
* Constants 
*************************************************************************/ 

/** return value for unsuccessful searches */ 
private static final OrderedListNode NOT_FOUND = null; 


/************************************************************************** 
* Attributes 
*************************************************************************/ 

/** current number of items in list */ 
private int theSize; 

/** reference to list header node */ 
private OrderedListNode head; 

/** reference to list tail node */ 
private OrderedListNode tail; 

/** current number of modifications to list */ 
private int modCount; 


/************************************************************************** 
* Constructors 
*************************************************************************/ 


/** 
* Create an instance of OrderedLinkedList. 
* 
*/ 
public OrderedLinkedList() 
{ 
    // empty this OrderedLinkedList 
    clear(); 
} 


/************************************************************************** 
* Methods 
*************************************************************************/ 


/* 
* Add the specified item to this OrderedLinkedList. 
* 
* @param obj  the item to be added 
*/ 
public boolean add(Comparable obj) 
{ 
    OrderedListNode newNode = new OrderedListNode(obj, null, null); 
    if(tail == null) { 
    tail = newNode; 
    head = tail; 
    modCount++; 
    return true; 

    } 
    if(((Comparable)(head.theItem)).compareTo(obj) > 0){ 
     //////////////////////////////////////// 
     //here is where my problem lies, I believe 
     ///////////////////////////////////////// 
     modCount++; 
     return true; 
    }else{ 


    tail.previous.next = newNode; 
    newNode.previous = tail.previous; 
    newNode.next = tail; 
    tail.previous = newNode; 
    modCount++; 
    return true; 
    } 
} 

/* 
* Remove the first occurrence of the specified item from this OrderedLinkedList. 
* 
* @param obj  the item to be removed 
*/ 
public boolean remove(Comparable obj) 
{ 
    if(head == null) return false; 
    if(((Comparable)(head.theItem)).compareTo(obj) == 0) { 
    if(head == tail) { 
     head = tail = null; 
     return true; 
    } 
    head = head.next; 
    return true; 
    } 

    if(head == tail)return false; 
    OrderedListNode ref = head; 
    while(ref.next != tail) { 
     if(((Comparable)(ref.next.theItem)).compareTo(obj) == 0) { 
      ref.next = ref.next.next; 
      return true; 
     } 
     ref = ref.next; 
    } 
    if(((Comparable)(tail.theItem)).compareTo(obj) == 0) { 
     tail = ref; 
     tail.next = null; 
     return true; 
    } 

    return false; 

} 


/** 
* Empty this OrderedLinkedList. 
*/ 
public void clear() 
{ 
    // reset header node 
    head = new OrderedListNode("HEAD", null, null); 

    // reset tail node 
    tail = new OrderedListNode("TAIL", head, null); 

    // header references tail in an empty LinkedList 
    head.next = tail; 

    // reset size to 0 
    theSize = 0; 

    // emptying list counts as a modification 
    modCount++; 
} 


/** 
* Return true if this OrderedLinkedList contains 0 items. 
*/ 
public boolean isEmpty() 
{ 
    return theSize == 0; 
} 


/** 
* Return the number of items in this OrderedLinkedList. 
*/ 
public int size() 
{ 
    return theSize; 
} 


/* 
* Return a String representation of this OrderedLinkedList. 
* 
* (non-Javadoc) 
* @see java.lang.Object#toString() 
*/ 
@Override 
public String toString() 
{ 
    String s = ""; 

    OrderedListNode currentNode = head.next; 

    while (currentNode != tail) 
    { 
     s += currentNode.theItem.toString(); 

     if (currentNode.next != tail) 
     { 
      s += ", "; 
     } 

     currentNode = currentNode.next; 
    } 

    return s; 
} 

private static class OrderedListNode<Comparable> { 

    Comparable theItem; 
    OrderedListNode<Comparable> next; 
    OrderedListNode<Comparable> previous; 

    public OrderedListNode(Comparable theItem, OrderedListNode<Comparable> previous, OrderedListNode<Comparable> next) { 
     this.theItem = theItem; 
     this.next = next; 
     this.previous = previous; 
    } 

} 

}

Answer 1

這行肯定是不對的

if(((Comparable)(head.theItem)).equals(obj)) { 

你應該使用Comparable.compareTo，除了應始終從頭部開始，去，直到你找到一個元素大於或等於OBJ和插入OBJ之前，這樣的事情

public boolean add(Comparable obj) { 
    modCount++; 
    if (head == null) { 
     head = new OrderedListNode(obj, null, null); 
     return true; 
    } 
    for (OrderedListNode current = head; current != null; current = current.next) { 
     if (((Comparable) (current.theItem)).compareTo(obj) >= 0) { 
      current.prev = new OrderedListNode(obj, current.prev, current); 
      return true; 
     } 
    } 
    tail.next = new OrderedListNode(obj, tail, null); 
    return true; 
}