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