我正在寻找一个为任意插入优化的列表数据结构，在任何索引下，但是我没有找到很多关于这个问题的信息，除了一些有趣的二叉树和许多痛苦的数组操作。
二叉树是有用的，但我认为广义列表更适合这个目的。不管怎么说，我不知道它们为什么不像树木那样被广泛使用。
然而，广义列表本身还不足以实现列表:它们必须有一个属性，可以保持它们清晰，在随机插入后不会在许多子列表中退化。
我提出这个属性: 泛化列表不能有与它的包含列表相等或更多项的子列表。如果这个属性是如果我们泄露子列表的元素，它就能被恢复
例如(1 2 3 (4 5 7 (9 1) 0))是"不稳定的"，因为它有一个比父列表有更多"槽"的子列表(不递归计算元素)。可以使用前面建议的属性重写为(1 2 3 4 5 7 (9 1) 0)。
同样，新元素将创建新的子列表，而不是直接添加到父列表中。例如:
如果在
的索引1中添加新元素"x"(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)
我的问题是:这个数据结构以前描述过吗?我的意思是，我认为它真的很有用，而且它几乎是微不足道的。如果它以前就存在，为什么不为人所知?它真的有用吗?有名字吗?我确实认为它很有用，但我可能错了。
我以持久的方式实现了它，但是我的代码(Java)有点混乱和丑陋，尽管它似乎可以工作并且也有文档记录。你觉得呢?
这听起来类似于跳跃列表:http://en.wikipedia.org/wiki/Skip_list