0

我正在尝试创建一个扩展 LinkedList 的 SortedLinkedList 类。此类应该将项目添加到 SortedLinkedList 并对其进行排序。

我正在尝试覆盖 boolean add(E obj) 方法，以便按排序顺序添加项目。

在 Stackoverflow 问题上，我发现了以下覆盖 add(E obj) 的方法：

public boolean add(E obj) {
    int index = 0;
    for( ; index<size() ; index++){
        E object= get(index);

        if(obj.compareTo(object) < 0){
            break;
        }
    }

    add(index, obj);
    return true;
};

我理解这个方法是如何工作的，但是我读过使用 ListIterator 比使用 get(index) 更有效。我一直在尝试使用 ListIterator，但似乎无法让一切正常工作。

这是我使用 Listiterator 所取得的进展，我确定它有问题，但我似乎无法弄清楚：

public boolean add(E obj)
{   
    add(size(), obj);
    ListIterator<E> iterator = listIterator();

    while(iterator.hasNext())
    {
        E object = iterator.next();
        if(obj.compareTo(object)<0)
        {
            //do something;
        }
    }
    return true;
}

关于如何使用迭代器对列表进行排序的任何建议？

4

1 回答 1

3

不要考虑使用迭代器对列表进行排序。考虑使用迭代器将新元素插入到已排序的列表中。

你的清单一开始是空的。添加第一个元素时，您将拥有一个元素的列表，根据定义，该列表已排序。如果您确保始终在正确的位置添加后续元素，那么列表将保持排序！

这正是使用的代码get所做的，但正如您所说的那样，这对于链表来说效率不高。您需要做的是使用迭代器重现该算法。

提示：列表迭代器允许您在当前位置添加元素。

于 2012-10-13T15:24:10.307 回答