次のドキュメントで確認できます。
java.util.AbstractList#removeRange
二次時間が必要であること:
この実装は、fromIndex の前に配置されたリスト反復子を取得し、範囲全体が削除されるまで、ListIterator.next に続いて ListIterator.remove を繰り返し呼び出します。注: ListIterator.remove に線形時間が必要な場合、この実装には 2 次時間が必要です。
しかし、なぜ??コード:
protected void removeRange(int fromIndex, int toIndex) {
ListIterator<E> it = listIterator(fromIndex);
for (int i=0, n=toIndex-fromIndex; i<n; i++) {
it.next();
it.remove();
}
}
私は線形のようです...しかし、私はこの種のアルゴリズムの初心者であるため、間違っている必要があります。それを理解するのを手伝ってください。