0

LinkedList を拡張する SortedLinkedList クラスを作成しようとしています。このクラスは、アイテムを SortedLinkedList に追加し、ソートすることになっています。

アイテムをソート順に追加するために、ブール値の 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;
};

このメソッドがどのように機能するかは理解していますが、get(index) を使用するよりも ListIterator を使用する方が効率的であることを読みました。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

イテレータを使用してリストをソートすることは考えないでください。イテレータを使用して、既にソートされたリストに新しい要素を挿入することを考えてみてください。

あなたのリストは空から始まります。最初の要素を追加すると、定義上、並べ替えられた 1 つの要素のリストが作成されます。後続の要素を常に適切な場所に追加するようにすると、リストはソートされたままになります!

これはまさに using のコードがget行うことですが、あなたの言う通り、連結リストでは効率的ではありません。あなたがする必要があるのは、反復子を使用してそのアルゴリズムを再現することです。

ヒント: リスト反復子を使用すると、現在の位置に要素を追加できます。

于 2012-10-13T15:24:10.307 に答える