在orderlinkedlist节点之间添加元素

Question

我在这个网站上查询了搜索引擎，但是我没有看到任何与我正在寻找的匹配的东西，所以我希望这个问题已经在其他地方得到了回答。我正试图完善我的添加方法为一个有序的LinkedList。程序的其余部分运行良好，当列表按照测试工具中指定的方式打印出来时，我希望对名称进行排序。

我的输出是在几次调用添加和删除线束后:

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