1

我在java中有这个自定义链表（不是java集合LinkedList）。它将项目添加到列表中的选定位置。

public void add(T item, int position) {
    Node<T> addThis = new Node<T>(item);
    Node<T> prev = head;
    int i;

    if(position <= 0) {
        //throw new ListException("Cannot add element before position 1");
        System.out.println("Error: Cannot add element before position 1.");
    }

    else if(position == 1) {
        addThis.setNext(head);
        head = addThis;
    } else {
        for(i = 1; i < position-1; i++) {
            prev = prev.getNext();
            if(prev == null) {
                //throw new ListException("Cannot add beyond end of list");
                System.out.println("Cannot add beyond end of list");
            }
        } // end for
        addThis.setNext(prev.getNext());
        prev.setNext(addThis);
    }
} // end add

我想要做的不是在选定位置添加项目，而是希望按字母顺序添加项目，以便整个列表在插入时按字母顺序排序。这是我到目前为止的代码，但我被卡住了。我怎样才能让它做我想做的事？

public void add(String title) {
    DvdNode addThis = new DvdNode(title);
    if (head == null) {
        head = addThis;
    } else if(title.compareToIgnoreCase(head.getTitle()) < 0) {
        // title comes before the current, so add as the first Dvd in the list
    } else {
        // the new title belongs somewhere later in the list
        // while i less than size of the list compare and insert if its greater
        // than what its being compared to
        // also update the links for the list so the whole list is still accessible
    } 
}

编辑：我终于让它工作了。我的解决方案基于 Byakuya 的解决方案。

public void add(Dvd item) {
  DvdNode addThis = new DvdNode(item);
  if(head == null) {
    head = addThis;
  } else if(item.getTitle().compareToIgnoreCase(head.getItem().getTitle()) < 0) {
      addThis.setNext(head);
      head = addThis;
    } else {
        DvdNode temp;
        DvdNode prev;
        temp = head.getNext();
        prev = head;
        while(prev.getNext() != null && item.getTitle().compareToIgnoreCase
            (prev.getNext().getItem().getTitle()) > 0) {
          prev = temp;
          temp = temp.getNext();
        }
        addThis.setNext(temp);
        prev.setNext(addThis);
      }
}
4

1 回答 1

1

创建这样的东西：

public void add(String title){
    DvdNode addThis = new DvdNode(title);
    DvdNode iter = head;
    DvdNode prev = null;

    while (iter && addThis.name.compareTo(iter.name) < 0){
        prev = iter;
        iter = iter.getNext();
    }
    addThis.setNext(iter);
    addThis.setPrev(prev);
    if (prev)
        prev.setNext(addThis);
    if (iter)
        iter.setPrev(addThis);
    if (head == null)
        head = addThis;
}

如果 head 为 null，那么您只需将 addThis next 和 prev 设置为 null 并更新 head。否则，迭代器将停止在第一个名称按字典顺序大于或等于您的字符串标题的元素处（因此，如果您的字符串标题是列表中最大的，则迭代器将停止在 null 处，您将插入元素作为列表中的最后一个，这是正确的），prev 将是 iter 之前的最后一个元素。然后进行正确的链接。

我的例子适合双向列表。如果您希望它适用于单向列表，只需删除 addThis 和 iter 的 Prev 设置。

于 2013-11-06T23:36:12.220 回答