任意のインデックスで任意の挿入用に最適化されたリスト データ構造を探していましたが、興味深いバイナリ ツリーと多くの面倒な配列操作を除いて、この問題に関する多くの情報が見つかりませんでした。
二分木は便利ですが、この目的には一般化リストの方が適していると思います。とにかく、なぜそれらが木ほど広く使われていないのかわかりません.
ただし、一般化されたリストは、リストを実装するのに十分ではありません。リストを明確に保ち、ランダムな挿入後に多くのサブリストで劣化しないプロパティが必要です。
私はこのプロパティを提案します:一般化されたリストは、それを含むリストと同じかそれ以上の項目を持つサブリストを持つことはできません。このプロパティに違反した場合、サブリストの要素を親リストにスピルすると復元できます。
たとえば、(1 2 3 (4 5 7 (9 1) 0))は「不安定」です。これは、親リストよりも多くの「スロット」を持つサブリストがあるためです (再帰的に要素を数えません)。前に提案されたプロパティを使用して(1 2 3 4 5 7 (9 1) 0)に書き換えることができます。
また、新しい要素は親リストに直接追加されるのではなく、新しいサブリストを作成します。例えば：
新しい要素「x」がインデックス 1 に追加された場合
(1 2 3 5)
それは
(1 ("x" 2) 3 4)
インデックス 1 に "y" を追加すると、次のようになります。
(1 (("y" "x") 2) 3 4)
これは「不安定」なので、次のように変換されます
(1 ("y" "x" 2) 3 4)
これも不安定なので、次のように変換されます。
(1 "y" "x" 2 3 4)
私の質問は次のとおりです。このデータ構造は以前に説明されていましたか? つまり、それは非常に便利で、ほとんど些細なことだと思います。以前に存在した場合、なぜそれほど知られていないのですか? それは本当に便利ですか？名前はありますか？便利だと思いますが、間違っているかもしれません。
私はそれを永続的な方法で実装しましたが、私のコード (Java) は少し面倒で醜いですが、動作しているようで、文書化もされています。どう思いますか？