List Data Structure C# Efficiency

Question

en este momento estoy usando List<short> como un buffer para mantener las cosas por un tiempo mientras se hace un cálculo para cada valor basado en otros valores más abajo del buffer. Luego me di cuenta de que esto probablemente no era muy eficiente ya que me dijeron que List<> es una lista enlazada, así que cada vez que hago whatever = myList[100]; lo peor es tener que saltar todos los otros nodos primero para obtener el valor que quiero. No quiero usar una matriz regular porque tengo un montón de Add() y Remove() dando vueltas en otros lugares del código. Entonces necesito una clase que herede IList<T> pero use una estructura de datos de matriz normal. ¿Alguien sabe una clase en .net que funciona de esta manera, así que no tengo que escribir la mía? ¡Intenté usar ArrayList pero no es genérico!

Answer 1

No, a List<T> es una colección genérica, no una lista vinculada. Si necesita agregar y eliminar funcionalidades, entonces List<T> es la implementación a la que la mayoría de las personas recurre por defecto.

Answer 2

List<T> no utiliza una implementación de lista vinculada. Internamente usa una matriz, por lo que parece ser exactamente lo que necesita. Tenga en cuenta que, debido a que es una matriz, Eliminar/insertar podría ser una operación costosa según el tamaño de la lista y el elemento de posición que se elimina/inserta: O (n). Sin saber más acerca de cómo lo está usando, es difícil recomendar una mejor estructura de datos.

Citando de la sección Observaciones del docs.

La clase List (T) es el equivalente genérico de la clase ArrayList. Implementa la interfaz genérica IList (T) usando una matriz cuyo tamaño se incrementa dinámicamente según sea necesario.

Answer 3

List<T> está respaldado por una matriz, no una lista vinculada. Los accesos indexados de un List<T> ocurren en tiempo constante.

Answer 4

Además de la respuesta correcta de tvanfosson, si alguna vez no está seguro de cómo funciona algo internamente, solo cargue el .NET Reflector y podrá ver exactamente cómo se implementan las cosas. En este caso, la perforación hasta el indexador de List<T> nos muestra el siguiente código:

public T this[int index] 
{ 
    get 
    { 
     if (index >= this._size) 
     { 
      ThrowHelper.ThrowArgumentOutOfRangeException(); 
     } 
     return this._items[index]; 
    } 
    // ... 

donde se puede ver que this._items[index] es una matriz del tipo genérico T.