Есть ли способ эффективно восстановить коллекцию на основе последовательности вставок / удалений?

Примечание : приведенный ниже код является C #, но на самом деле ответ на любом языке будет быть полезным для меня.

Предположим, вместо реальной коллекции (например, , a List ), у меня есть последовательность из операций , каждая из которых выглядит примерно так:

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

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

Есть ли способ эффективно "восстановить «коллекция, основанная на последовательности таких операций?

В частности, я стараюсь избежать очевидной (неэффективной) реализации, по сути, просто создания List и вызова Insert и RemoveAt - обе O (N) операции - для каждого элемента.

Update : Допустим, «последовательность» операций на самом деле представляет собой конкретную коллекцию, количество которой известно и который доступен случайным образом по индексу (например, как ListOperation [] , например). Позволять' s также говорят, что фактическое количество результирующей коллекции уже известно (но на самом деле, это было бы тривиально вычислить за O (N), подсчитывая вставки и удаления). Есть какие-нибудь другие идеи?