A data structure traversable by both order of inse

Question

Is there a data structure that can be traversed in both order of insertion and order of magnitude in O(n) with at most O(log(n)) insertion and deletion?

In other words given elements 5, 1, 4, 3, 2 (inserted in this order), it can be traversed either as 1,2,3,4,5 or as 5,1,4,3,2 in O(n) time.

Of course I could use an array and simply sort it before traversing, but this would require an O(n*log(n)) pre-traversal step. Also, I could use a multi-linked list to achieve O(n) traversal, but in this case the insertion and deletion operations will also take O(n) since I cannot guarantee that the newest element will necessarily be the largest.

If there exists such a data structure, please provide me with a formal name for it so that I may research it further, or if it doesn't have one, a brief surface-level description would be appreciated.

Thank you

Answer 1

One solution that also permits sublinear deletion is to build a data structure D that uses a linked list D.L for the traversal in order of insertion, and a sorted tree D.T for the traversal in order of magnitude. But how to link them to additionally achieve a remove operation in sublinear time? The trick is that D.T should not store the values, but just a reference to the corresponding linked list element in D.L.

Insertion: Append to D.L in time O(1), and insert a reference to the appended element into D.T in time O(log(n)). Any comparisons in D.T are of course made on the referenced values, not by the references themselve)

Traverse by order of insertion (or backwards): simply traverse D.L in time O(n) linearly

Traverse by order of magnitude (or backwards): simply traverse D.T in time O(n) by tree-walk

Deletion: first find&remove the element in D.T in time O(log n), which also gives you the correct element reference into D.L, so it can be removed from D.L in time O(1).

Answer 2

The commenters are right: your best bet is to store your objects twice: once in a linked list (order of insertion) and once in a binary tree (intrinsic sort order).

This is not as bad as it may sound as you do not have to copy the objects, thus the only cost is the list/tree scaffolding and that would cost you 4 machine words per object you store.

Answer 3

You don't even really need two data structures. Just use a binary tree, but rather than inserting your object, wrap it in an object which also contains pointers to the previous and next objects. This is fairly trivial to do in main stream languages like java where you can use the default tree implementation with a comparator to order your tree by a property.

As long as you keep a reference to the first and last element you can traverse them in order using the internal pointers of the object.