使用快速节点顺序查询的链接列表

Question

我们使用双链表数据结构来存储一些无序数据（数据本身是无序的，但是链接列表中的节点顺序是相关的）。此数据结构上的一个常见操作是NodeBeforeNode（节点N1，节点N2），它在列表中给出两个节点指针，并确定它们中的哪一个在另一个之前。

此操作需要线性时间，因为它需要遍历列表以查找其他元素，这非常缓慢。为了加快速度，我们已经缓存了节点本身中每个节点的序号，并根据需要刷新了这个缓存。但是，刷新缓存是线性的，而修改列表并访问缓存的操作往往非常缓慢。

我在寻找加快此行为的建议。我基本上需要一个数据结构，其允许在恒定的或对数时间所有以下操作：

1. 插入（后或节点之前）
2. 删除一个节点的
3. NodeBeforeNode

灿任何人都会提出一个像支持相同结构的链接列表？

谢谢！

Answer 1

实施经修改的二叉搜索树，

struct node { 
    /*add your data*/ 
    node *parent; 
    node *left; 
    node *right; 
} 

中，你可以通过父指针和插入访问前一个元素，搜索和删除时间为O（LOGN）

Answer 2

也许你应该考虑用某种索引更新节点？插入和删除节点是肯定的线索，该列表应该是链表实现。我建议将新变量添加到表示其在列表中的位置的节点中。

所以基本上：

• 插入到底应该有索引每一个新项目= last_index + CONST
• 插入表应该有邻居

该指数=算术平均值每一个新项目当然，只有当给定两个节点在同一个列表上时才有效。比较它们将是简单的指数比较。

请注意，该索引应该是浮点数。这个简单的方案假设，有无限可分的。如果你的程序运行很长时间，也许应该运行一些定期的工作人员乘以索引值？