Linked List with fast node order querying

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 li开发者_如何学JAVAst 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:

1. Insertion (after or before a node)
2. Deletion of a node
3. NodeBeforeNode

Can anyone suggest a linked-list like structure which supports the same?

Thanks!

---

Implement a modified Binary search tree,

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

in which you can access the previous element via a parent pointer and Insertion, searching and deletion time is in O(logn)

---

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.

So basically:

• every new item inserted into end should have index=last_index+CONST
• every new item inserted into list should have index=arithmetic mean of neighbours

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?