C# Lista eliminar del final, realmente O (n)?

Question

He leído un par de artículos que dicen que List.RemoveAt() está en O (n) hora.

Si hago algo como:

var myList = new List<int>(); 

/* Add many ints to the list here. */ 

// Remove item at end of list: 
myList.RemoveAt(myList.Count - 1); // Does this line run in O(n) time? 

Extracción desde el final de la lista debe ser O (1), ya que sólo tiene que disminuir el número de lista.

¿Necesito escribir mi propia clase para tener este comportamiento, o eliminar el elemento al final de una lista C# que ya funciona en O (1) vez?

Answer 1

En general List<T>::RemoveAt es O (N) debido a la necesidad de desplazar elementos después del índice hacia arriba de una ranura en la matriz. Sin embargo, para el caso específico de la eliminación de la final de la lista no se necesita ningún cambio y, en consecuencia, O (1)

Answer 2

Esto debe darle una idea

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

Answer 3

Extracción último elemento será realmente O(1) operación dado que solo en este caso List no cambia los siguientes elementos en el conjunto. Aquí es un código de reflector:

this._size--; 
if (index < this._size) // this statement is false if index equals last index in List 
{ 
    Array.Copy(this._items, index + 1, this._items, index, this._size - index); 
} 
this._items[this._size] = default(T); 

Answer 4

Me parece que si esto era realmente relevantes para su aplicación, se podría haber medido en menos tiempo del que se tomó para hacer la pregunta. Y ahora tiene al menos dos respuestas contradictorias, por lo que tendrá que probarlo de todos modos.

Lo que quiero decir es que, a menos que los documentos de MSDN digan que removeAt es O (1) para los elementos al final de la lista, no podría contar con que funcione de esa manera, y podría cambio en cualquier actualización de .NET dada. Para el caso, el comportamiento podría ser diferente para diferentes tipos, para todo lo que sabes.

If List es la estructura de datos "natural" que se debe usar, y luego úselo. Si eliminar elementos de la Lista termina siendo un punto caliente en su perfil, entonces tal vez sea el momento de implementar su propia clase.