0

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

Vladimir
  • 225
  • 1
  • 11
  • 1
    What about list + binary search tree? – David Eisenstat Jul 01 '15 at 13:09
  • 2
    I'd be surprised if such a structure existed. You can of course simply build two sort-trees, for example, or a sort-tree and a linked list. – G. Bach Jul 01 '15 at 13:10
  • @DavidEisenstat Yes, I was thinking along those same lines, but I'm not sure how I would connect them so that when I remove an element from one, it would be removed from the other in sub-O(n) time. – Vladimir Jul 01 '15 at 13:14
  • @G.Bach Me too, but I figured I'd ask just in case. – Vladimir Jul 01 '15 at 13:18
  • The tree and list combo might actually work, but I would need careful about how I link the elements. – Vladimir Jul 01 '15 at 13:19

3 Answers3

3

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

cubic lettuce
  • 6,301
  • 3
  • 18
  • 25
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.

sds
  • 58,617
  • 29
  • 161
  • 278
  • I accepted another answer for its explanation, but I still really appreciate your insight into the cost of scaffolding as this helps me get an idea of the how this will affect the performance. Thank you! – Vladimir Jul 01 '15 at 14:44
1

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.

phil_20686
  • 4,000
  • 21
  • 38
  • Great idea Phil! Thanks you! For me it might be a little harder to implement because I need to do this in C, but this trick could be helpful to others that may come across this question. :) Thanks! – Vladimir Jul 01 '15 at 14:50