Добавить элементы между узлами Упорядоченный LinkedList

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