java创建排序链表类

Question

我试图创建一个SortedLinkedList类来扩展LinkedList。此类应将项目添加到SortedLinkedList并对其进行排序

我试图重写布尔添加（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;
}

关于如何使用迭代器对列表进行排序，有什么建议吗

Answer 1

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

您的列表将以空开头。添加第一个元素时，将有一个元素列表，根据定义，该列表已排序。如果确保始终在正确的位置添加后续元素，则列表将保持排序

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

提示：列表迭代器允许您add an element at the current position