3

リンクされたリストのポイントは、どこにでも効率的に挿入 (および削除) できるようにすることであるため、Java の LinkedList でこれを見つけることを期待していました (挿入または削除する場所への何らかのポインターがあると仮定します)。私はAPIで何も見つけていません。私は何かを見落としていますか？

これに最も近いのは、ListIterator の add メソッドと remove メソッドです。ただし、これにはいくつかの制限があります。特に、API によると、基礎となる LinkedList が remove によって変更されるとすぐに、他の反復子は無効になります。これは私のテストでも生まれました。次のプログラムでは、IllegalStateException が発生します。

import java.util.*;
public class RemoveFromLinkedList {
    public static void main(String[] args) {
        LinkedList<Integer> myList= new LinkedList<Integer>();
        for (int i = 0; i < 10; ++i) {
            myList.add(i);
        }

        ListIterator<Integer> i1 = myList.listIterator();
        ListIterator<Integer> i2 = myList.listIterator();
        for (int i = 0; i < 3; ++i) {
            i1.next();
            i2.next();
        }

        System.out.println("i1.next() should be 3: " + i1.next());
        i1.remove();
        i1.remove();

        // Exception!
        System.out.println("i2.next() should be 5: " + i2.next());
    }
}

理想的には、私が期待しているのは次のようなものです。

// In my imagination only. This is the way Java actually works, afaict.

// Construct two insertion/deletion points in LinkedList myLinkedList.
myIterator = myLinkedList.iterator();
for (...) {
 myIterator.next();
}
start = myIterator.clone();
for (...) {
 myIterator.next();
}

// Later...

after = myLinkedList.spliceAfter(myIterator, someOtherLinkedList);
// start, myIterator, and after are still all valid; thus, I can do this:
// Removes everything I just spliced in, as well as some other stuff before that.
myLinkedList.remove(start, after);
// Now, myIterator is invalid, but not start, nor after.

C++ のリストクラス (テンプレート) には、このようなものがあります。すべてのイテレータではなく、移動された要素を指すイテレータのみが無効になります。

4

3 に答える 3

2

If you remove something with an iterator you cann still continue to use that same iterator. It's possible to do

iterator.remove();
iterator.next();
iterator.remove();
iterator.next();

That's the closest thing as far as I know.

于 2012-10-21T22:44:49.967 に答える
2

で面白いことができますList.subList(startIndex, endIndex)。これにより、「ソース」リストの範囲全体をクリアできます。at the sublist を使用addAllして、ソース リストに新しいものを挿入することもできます。

これLinkedListに効率的な実装があるかどうか-わかりません。

于 2012-10-21T22:57:32.250 に答える
1

java.util.LinkedListを使用すると、後で効率的に操作するためにリスト内の場所を参照する唯一の方法はイテレーターであり、基になるリストがこのイテレーター以外のものによって変更された場合、イテレーターは無効になります。

その機能が本当に必要な場合は、Java APIの先を見据えるか、自分で作成する必要があります。

于 2012-10-21T23:27:39.247 に答える