java.util パッケージ内のデータ構造を探しています。次の要件を満たす必要があります。
- 要素の数は（理論的には）無制限です。
- 要素は昇順に並べられます。
- n 番目の要素を (高速に) 取得できます。
- n 番目の要素を削除できます (高速)。
インデックス可能なスキップ リストが見つかると思っていましたが、見つかりませんでした。私が述べた要件を満たすデータ構造はありますか?
ベストアンサー1
Java 標準ライブラリにはそのようなコンテナはありません。
Listこれらの特性を持つデータ構造が必要な場合、実装（通常は ですArrayListが、何でも構いません）を使用し、挿入はすべて で行います。Collections.binarySearch。
ソートされたリストを再利用可能なクラスとしてカプセル化する必要がある場合は、List インターフェイスを実装し、すべてのメソッドを「標準」List 実装に委譲します (コンストラクターにパラメーターとして渡すこともできます)。すべての挿入メソッド (add、addAll、set、Iterator の remove) を例外 ( ) をスローして実装し、誰も「常にソート」プロパティを破ることができないようにします。最後に、挿入を行うために使用するUnsupportedOperationExceptionメソッドを提供します。insertSortedCollections.binarySearch