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
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).