ソートされた LinkedList の実装を最適化しています。
要素を挿入するには、リストをトラバースし、正しいインデックスが得られるまで各要素を比較してから、ループを中断して挿入します。
O(n + (n capped at size()/2)) から O(n) に挿入を減らすために、リストをトラバースすると同時に要素を挿入できる他の方法があるかどうかを知りたい.
ListIterator は、その add() メソッドのおかげで、ほぼ後になりますが、残念ながら、リスト内に挿入と等しい要素がある場合、挿入はリスト内のそれらの後に配置する必要があります。この ListIterator を実装するには、持っていない peek() が必要です。
編集：答えはありますが、多くの人が正しく理解していないため、とにかくこれを追加します： 挿入ポイントと挿入を検索しています。これらの組み合わせはO（n）よりも高くなります
さまざまな粒度で複数のリンクされたリストを使用して実装されるスキップ リストを検討することもできます。たとえば、レベル 0 のリンクされたリストにはすべての項目が含まれ、レベル 1 は平均して 2 つおきの項目にのみリンクし、レベル 2 は平均して 4 つおきの項目にのみリンクするなど....完全一致が見つかります。このロジックは二分探索に似ています。したがって、検索と挿入は O(log n ) 操作です。
Java クラス ライブラリの具体的な例は次のとおりですConcurrentSkipListSet(ただし、ここでは直接使用できない場合があります)。
私はPéterTörökの提案を支持しますが、イテレータアプローチのために何かを追加したいと思います:
リストを逆方向に反復するメソッドをListIterator提供することに注意してください。previous()したがって、最初に大きい要素が見つかるまで繰り返し、次に前の要素に移動して を呼び出しますadd(...)。最後にヒットした場合、つまりすべての要素が小さい場合は、戻らずに呼び出しadd(...)ます。
私には答えがありますが、多くの人が正しく理解していないので、とにかくこれを追加します。挿入ポイントを検索して挿入します。これらを組み合わせたものはよりも高くなり
O(n)ます。
順序付け関数によって指定された順序で繰り返すことができる（おそらく）一意でない要素のコレクションを維持する必要があります。これは、さまざまな方法で実現できます。（以下では、「総挿入コスト」を使用Nして、最初は空のデータ構造に多数の要素を挿入するコストを意味します。）
単一または二重にリンクされたリストは、O(N^2)合計挿入コスト（位置を見つけて挿入を実行するステップを組み合わせるかどうかに関係なく！）とO(N)反復コストを提供します。
TreeSetは、O(NlogN)合計挿入コストとO(N)反復コストを提供します。ただし、重複がないという制限があります。
ツリーベースのマルチセット（例TreeMultiset）は、TreeSetと同じ複雑さですが、重複が可能です。
スキップリストのデータ構造も、前の2つと同じ複雑さを持っています。
明らかに、複雑さの尺度は、リンクリストを使用するデータ構造は、Nが大きくなるにつれてパフォーマンスが最悪になることを示しています。この特定の要件グループの場合、コレクションにアクセスするスレッドが1つだけであると仮定すると、適切に実装されたツリーベースのマルチセットがおそらく最適です。コレクションが多くのスレッドで頻繁に使用されている場合（そしてそれがセットである場合）、ConcurrentSkipListSetおそらくaの方が適しています。
また、「ビッグO」の測定値がどのように組み合わされるかについて誤解しているようです。あるアルゴリズムの1つのステップと、これO(N)もある2番目のステップがあるO(N)場合、2つのステップを組み合わせたものはまだO(N)....「以上」ではありませんO(N)。これは「ビッグO」の定義から導き出すことができます。（詳細については退屈させませんが、数学は単純です。）