我想创建一个带有顺序序列(整数属性)的双向链表，这样按顺序排序可以创建一个实际上等同于链表的数组。
given: a <-> b <-> c
a.index > b.index
b.index > c.index
该索引需要有效地处理任意数量的插入。
是否有已知的算法来完成此操作？ 问题是当列表变大并且索引序列变得紧凑时。在那种情况下，必须扫描列表以恢复松弛。 我只是不确定这应该如何完成。理想情况下会有某种自动平衡，以便这种借贷既快速又罕见。
将所有左索引或右索引更改为 1 以便为插入腾出空间的简单解决方案是 O(n)。
我更喜欢使用整数，因为我知道数字在 float 中的可靠性往往会降低，因为它们在大多数实现中接近零。
最佳答案
这是我最喜欢的问题之一。在文献中，它被称为“在线列表标签”，或简称为“列表标签”。维基百科上有一点:https://en.wikipedia.org/wiki/Order-maintenance_problem#List-labeling
可能对您的目的实用的最简单的算法是这里的第一个:https://www.cs.cmu.edu/~sleator/papers/maintaining-order.pdf .
它以分摊的 O(log N) 时间处理插入，并且要管理 N 个项目，您必须使用大到足以容纳 N^2 的整数。几乎所有实际情况下，64 位整数都足够了。
关于algorithm - 链表的简单排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40986849/