Is there any way to efficiently reconstruct a collection based on a sequence of inserts/removals?

Question

Note: the below code happens to be C#, but really an answer in any language would be helpful for me.

Suppose rather than an actual collection (e.g., a List<T>), I have a sequence of operations, each looking something like this:

struct ListOperation<T>
{
    public enum OperationType { Insert, Remove }

    public OperationType Type;
    public T Element; // irrelevant for OperationType.Remove
    public int Index;
}

Is there some way to efficiently "reconstruct" a collection based on a sequence of such operations?

In particular, I'm looking to avoid the obvious (inefficient) implementation of basically just creating a List<T> and calling Insert and RemoveAt—both O(N) operations—for every element.

---

Update: Let's say the "sequence" of operations is in fact a concrete collection whose count is known and which is randomly accessible by index (so, like a ListOperation<T>[], for example). Let's also say the actual count of the resulting collection is already known (but really, that would be trivial to figure out in O(N) anyway, by counting insertions and removals). Any other ideas?

Answer 1

I think you can do this in O(n lg n) by using an indexed balanced binary tree (a binary tree where each node stores the number of nodes to its left and right). With this structure, you can get worst-case O(lg n) insertion or deletion at any point by walking the tree to find the position at which the new element belongs, then doing whatever fixup is necessary to maintain the balance condition (for example, if it's a red-black tree, you'd do a red-black tree fixup).

Given this setup, you could replay all the operations into a tree structure like this in O(n lg n) because each individual operation takes at most O(lg n) to complete. Once you have the tree, you can then do an inorder traversal of the elements to get them back in the proper order, and can append all the values to a resulting list in O(n) time, for a net of O(n lg n).

I'm going to think about this more and see if I can come up with a way of doing this in linear time. In the meantime, this at least shows that it's possible to do this in subquadratic time.