有大量关于无锁双向链表的研究。同样，在无锁跳过列表上也有大量研究。然而，据我所知，没有人管理过无锁的双向链接跳过列表。有没有人知道任何相反的研究，或者是这种情况的原因？
编辑：特定场景是用于构建快速分位数（50%、75% 等）累加器。样本在 O(log n) 时间内被插入到跳过列表中。通过维护当前分位数的迭代器，我们可以在 O(1) 时间内将插入的值与当前分位数进行比较，并且可以轻松确定插入的值是在分位数的左侧还是右侧，以及分位数的多少结果需要移动。左移需要前一个指针。
据我了解，面对同时插入和删除的多个线程，任何困难都来自保持先前的指针一致。我想这个解决方案几乎肯定会巧妙地使用指针标记。
但是你为什么会做这样的事情？我实际上并没有坐下来弄清楚跳过列表是如何工作的，但是根据我的模糊理解，你永远不会使用前面的指针。那么为什么要维护它们的开销呢？
但如果你想，我不明白为什么你不能。只需将单链表替换为双向链表即可。双向链表在逻辑上是连贯的，所以都是一样的。
我有一个想法给你。我们使用“光标”在跳过列表中查找项目。光标还保留了到达该项目的轨迹。我们将这条线索用于删除和插入——它避免了执行这些操作的第二次搜索，并且它嵌入了在进行遍历时看到的列表的版本号。我想知道您是否可以使用光标更快地找到上一项。
您必须在光标上上升一个级别，然后搜索仅比您的项目少一点的项目。或者，如果搜索到了链表的最低级别，只需在遍历时保存 prev ptr。最低级别可能有 50% 的时间用于查找您的项目，因此性能会不错。
嗯……现在想想，光标似乎有 50% 的时间有 prev ptr，25% 的时间需要从 1 级向上再次搜索，12.% 2 级向上等。所以在在不常见的情况下，您几乎必须再次完全进行搜索。
我认为这样做的好处是您不必弄清楚如何“无锁”维护双链跳过列表，并且在大多数情况下，您可以显着降低定位前一个项目的成本。
作为维护反向链接的替代方法，当需要更新分位数时，您可以进行另一次搜索以找到其键小于当前键的节点。正如我刚刚在对 johnnycrash 的评论中提到的那样，可以构建在每个级别找到的最右边节点的数组 - 并且可以由此加速第二次搜索。（Fomitchev 的论文提到这是一种可能的优化。）