Насколько дорогой список .RemoveAt(0) для общего списка?

С#,.NET4.

У нас есть критический код производительности, который вызывает некоторые проблемы. Это своего рода измененная очередь, которая на самом деле поддерживается списком. Мне было интересно, как дорого стоит элемент с индексом 0. Вопросы, которые приходят на ум, следующие:

В зависимости от того, как поддерживается резервная копия, выполняются ли какие-либо выделения/освобождения памяти после удаления в RemoveAt() для компенсации нового размера списка? Я знаю, например, что изменение размера массива может быть дорогостоящим (относительно говоря).
Я всегда представлял себе, что списки ведут себя как связанные списки, так что удаление элемента в нулевой позиции означает просто наличие ссылки на начало списка, скорректированную с предыдущего нулевого элемента на то, что раньше было первым (но теперь является первым элементом). Но мое "воображение" и реальность не всегда в строю.

Я всегда предполагал, что RemovedAt был O (1) для списков. Это тот случай?

Ответ 1

List<T> поддерживается простым массивом плюс поле size, которое указывает, какая часть массива фактически используется. (для обеспечения будущего роста). Массив не изменяется, если вы не добавляете слишком много элементов или вызываете TrimExcess.

Remove - O(n), так как ему нужно сдвинуть остальную часть списка на один.

Вместо этого вы можете использовать LinkedList<T> (если вы не используете произвольный доступ) или написать собственный список, который отслеживает пустую часть спереди.

Ответ 2

Это O (n). Он даже говорит об этом MSDN.

Этот метод является операцией O (n), где n является (Count-index).

Ответ 3

Из того, что я могу сказать, это должна быть операция O (n). Внутри он использует Array.Copy (что является операцией O (n)), чтобы скопировать элементы после 0 обратно в массив поддержки списка. Из рефлектора:

public void RemoveAt(int index) {
    if (index >= this._size) {
        ThrowHelper.ThrowArgumentOutOfRangeException();
    }
    this._size--;
    if (index < this._size) {
        Array.Copy(this._items, index + 1, this._items, index, this._size - index);
    }
    this._items[this._size] = default(T);
    this._version++;
}

Итак, для любого действительного индекса массива я он копирует все последующие элементы из я + 1 в i.