链表的简单排序
Simple ordering for a linked list
我想创建一个带有顺序序列（整数属性）的双向链表，这样按顺序排序可以创建一个实际上等同于链表的数组。
given: a <-> b <-> c
a.index > b.index
b.index > c.index
该索引需要有效地处理任意数量的插入。
是否有已知的算法来完成此操作？
问题是当列表变大并且索引序列变得紧凑时。在那种情况下，必须扫描列表以恢复松弛。
我只是不确定这应该如何完成。理想情况下会有某种自动平衡，以便这种借贷既快速又罕见。
将所有左索引或右索引更改为 1 以便为插入腾出空间的简单解决方案是 O(n)。
我更喜欢使用整数，因为我知道数字在大多数实现中趋近于零时在浮点数中的可靠性往往会降低。
这是我最喜欢的问题之一。在文献中，它被称为 "online list labeling"，或简称为 "list labeling"。维基百科上有一点：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 位整数就足够了。
我最终寻求的是 roll-my-own 解决方案，因为看起来算法希望在插入下一个节点之前将整个列表存储在内存中。那可不行。
我的想法是借用一些算法的思路。我所做的是将 ID 设为整数并排序为长整数。然后该算法是惰性的，将条目填充到任何适合的地方。一旦它在某个地方的某个小团块中用完 space ，它就会开始从团块上下扫描并尝试建立均匀的间距，这样如果扫描了 n 个项目，它们就需要在它们之间共享 n^2 填充.
理论上这将意味着随着时间的推移列表将被完美填充，并且考虑到我的 ID 是整数并且我的排序顺序是长整数，永远不会出现您无法实现 n^2 的情况填充。我不能说出运算次数的上限，但我的直觉告诉我，通过以 1/多项式频率进行多项式运算，我会做得很好。
我想创建一个带有顺序序列（整数属性）的双向链表，这样按顺序排序可以创建一个实际上等同于链表的数组。
given: a <-> b <-> c
a.index > b.index
b.index > c.index
该索引需要有效地处理任意数量的插入。
是否有已知的算法来完成此操作？ 问题是当列表变大并且索引序列变得紧凑时。在那种情况下，必须扫描列表以恢复松弛。 我只是不确定这应该如何完成。理想情况下会有某种自动平衡，以便这种借贷既快速又罕见。
将所有左索引或右索引更改为 1 以便为插入腾出空间的简单解决方案是 O(n)。
我更喜欢使用整数，因为我知道数字在大多数实现中趋近于零时在浮点数中的可靠性往往会降低。
这是我最喜欢的问题之一。在文献中，它被称为 "online list labeling"，或简称为 "list labeling"。维基百科上有一点：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 位整数就足够了。
我最终寻求的是 roll-my-own 解决方案，因为看起来算法希望在插入下一个节点之前将整个列表存储在内存中。那可不行。
我的想法是借用一些算法的思路。我所做的是将 ID 设为整数并排序为长整数。然后该算法是惰性的，将条目填充到任何适合的地方。一旦它在某个地方的某个小团块中用完 space ，它就会开始从团块上下扫描并尝试建立均匀的间距，这样如果扫描了 n 个项目，它们就需要在它们之间共享 n^2 填充.
理论上这将意味着随着时间的推移列表将被完美填充，并且考虑到我的 ID 是整数并且我的排序顺序是长整数，永远不会出现您无法实现 n^2 的情况填充。我不能说出运算次数的上限，但我的直觉告诉我，通过以 1/多项式频率进行多项式运算，我会做得很好。