<分区>
我一直在寻找一个针对任意插入优化的列表数据结构，在任何索引处，但我没有找到很多关于这个问题的信息，除了一些有趣的二叉树和很多痛苦的数组操作。
二叉树很有用，但我认为广义列表更适合此目的。无论如何，我不知道为什么它们不像树那样被广泛使用。
但是，广义列表本身不足以实现列表:它们必须具有一个属性，可以使它们保持清晰，在随机插入后不会在大量子列表中退化。
I propose this propery: A Generalized list cannot have sublist with equal or more items than its containing list. If this property is violated, it can be restored if we spill the elements of the sublist in the parent list.
例如 (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)
如果将“y”添加到索引 1，则它将是
(1 (("y" "x") 2) 3 4)
这是“不稳定的”，所以它会被转换成
(1 ("y" "x" 2) 3 4)
这也是不稳定的，所以它会被转化为
(1 "y" "x" 2 3 4)
我的问题是:之前是否描述过这种数据结构？我的意思是，我认为它真的很有用，而且几乎微不足道。如果它以前存在，为什么不那么为人所知？ 它真的有用吗？它有名字吗？我确实认为它很有用，但我可能错了。
我implemented it in a persistent fashion ，但我的代码 (Java) 有点乱和丑陋，尽管它似乎可以工作并且也有记录。你怎么看？