我们使用的是双向链表数据结构的一些无序的数据存储（数据本身是无序的，但是在链接列表中的节点顺序是相关的）。 在此数据结构的常见的操作是NodeBeforeNode（节点N1，节点N2），这是考虑在列表中的两个节点指针，并且确定它们中的哪先于其他。
此项操作需要线性时间，因为它需要遍历列表中找到其他的元素，这是非常缓慢的。 加快这我们已经缓存节点本身内的每个节点的序号，并根据需要刷新该缓存。 但是，刷新缓存是线性的，其或者修改列表，并访问该缓存操作往往是非常缓慢的。
我要找的建议，以加快这一行为。 我基本上需要一个数据结构，其允许在恒定的或对数时间所有以下操作：
- 插入（或后一个节点之前）
- 一个节点的删除
- NodeBeforeNode
任何人都可以提出一个链表一样，它支持相同的结构？
谢谢！
实施经修改的二叉搜索树，
struct node {
/*add your data*/
node *parent;
node *left;
node *right;
}
可以在其中通过一个父指针和插入访问以前的元件，检索和删除时间是在O（logn）时间
也许你应该考虑以某种指数的更新节点？ 插入和节点的缺失是肯定的线索，该名单应该是LinkedList的实现。 我建议增加新的变量为表示其在列表中的位置的节点。
所以基本上：
- 插入到年底每一个新的项目应具有指数= last_index + CONST
- 插入到列表中的每个新项目应该有邻居指数=算术平均值
当然，这只能如果给两个节点是相同的名单上。 比较起来会比较简单的指标。
请注意，该指数应该浮点数。 这个简单的情景假设，有无限可分的。 如果你的程序将运行很长一段时间，也许有些乘以指标值的定期工人应该运行？
