具有快速节点顺序查询的链接列表 [英] Linked List with fast node order querying
问题描述
我们正在使用双链列表数据结构来存储一些无序数据(数据本身是无序的，但是链接列表中的节点顺序是相关的).在此数据结构上的常见操作是NodeBeforeNode(节点N1，节点N2)，该操作在列表中具有两个节点指针，并确定它们中的哪个先于另一个.
We are using a Doubly Linked List data structure to store some unordered data (The data as such is unordered, however the node order in the link list is relevant). A common operation on this data structure is NodeBeforeNode(Node N1, Node N2), which is given two node pointers in the list and determines which of them precedes the other.
此操作需要线性时间，因为它需要遍历列表以查找其他元素，这非常慢.为了加快速度，我们已经缓存了节点本身内每个节点的序号，并根据需要刷新了此缓存.但是，刷新缓存是线性的，并且交替修改列表和访问该缓存的操作往往很慢.
This operation takes linear time as it needs to traverse the list to find the other element, which is pretty slow. To speed this up we have cached the ordinal number of each node within the node itself, and refreshed this cache as required. However, refreshing the cache is linear, and operations which alternatively modify the list and access this cache tend to be very slow.
我正在寻找加快此行为的建议.我基本上需要一个数据结构，该结构允许在恒定或对数时间内进行以下所有操作:
I am looking for suggestions to speed up this behavior. I basically need a data structure which allows all the following operations in constant or logarithmic time:
- 插入(在节点之后或之前)
- 删除节点
- NodeBeforeNode
有人可以建议像链表这样的结构来支持它吗?
Can anyone suggest a linked-list like structure which supports the same?
谢谢！
推荐答案
也许您应该考虑使用某种索引来更新节点?节点的插入和删除无疑是线索，该列表应该是链表的实现.我建议将新变量添加到表示其在列表中位置的节点中.
Maybe you should consider updating nodes with some kind of index? Insertion and deletion of node is for sure clue, that list should be the linkedlist implementation. I suggest adding new variable into node representing its position in list.
所以基本上:
- 插入到末尾的每个新项目都应具有index = last_index + CONST
- 插入列表中的每个新项目都应具有index =邻居的算术平均值
这当然仅在给定两个节点在同一列表中的情况下有效.比较它们将是简单的索引比较.
This of course works only if given two nodes are on the same list. Comparing them would be simple index comparing.
请注意，该索引应为浮点数.这个简单的场景假设存在无限可分割的部分.如果您的程序要长时间运行，也许应该运行一些乘以索引值的定期工作程序?
Please notice, that index should be floating point number. This simple scenario assumes, that there are infinitely dividable. If your program would be running long time, maybe some periodic worker which multiplies indexes values should be run?
这篇关于具有快速节点顺序查询的链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
