我需要一个包含有序列表的数据结构。我需要一个insert、delete和getposition操作。
getPosition操作经常在连续的元素上调用，例如我有一个列表：
[a0, a1, …, ak, ak', …, an]
我经常需要得到
ak的索引，然后是ak'的索引。我在想一个类似于splay树的算法，但是它也可以有效地移动被访问元素的邻居，但是我找不到任何引用。你有什么建议吗？
编辑：
我还需要一个快速插入+删除O（log（n））中的某些内容就足够了。
最佳答案
来一杯Skip List怎么样这将允许您保持一个有序的列表，并为插入、删除和搜索提供O（log n）性能（平均）。
在优化搜索元素k+1方面，也许只需缓存最后一个搜索的索引并从那里开始搜索。
关于algorithm - 良好的数据结构来保存 list ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31140774/