¿Cómo se mapea internamente la Lista <T>?

Question

¿Se trata internamente como una matriz o el CLR la trata como un tipo totalmente diferente?

Estoy tratando de implementar valores enteros en la lista.

List<int> lst = new List<int>(); 
lst.Add(3); 
lst.Add(4); 

vs

que crear una matriz de enteros

int[] arr = new int[2]; 
arr[0] = 3; 
arr[1] = 4; 

Array Devuelve mejores resultados en tiempo envergadura. Entonces, ¿por qué la gente prefiere List <>.

Answer 1

List<> es una implementación de una estructura de datos, que se encarga de asignar memoria según demanda; permite la inserción y eliminación en cualquier índice, etc. Por lo tanto, es mucho más conveniente que una matriz simple.

Debajo del capó, la implementación actual de List<> usa una matriz para el almacenamiento, y la sobrecarga cuando se realizan operaciones similares a arreglos es mínima. La conveniencia adicional generalmente vale la poca diferencia de rendimiento (si es que es relevante). Agregar elementos suele ser más rápido porque la lista asigna trozos de memoria y no requiere una nueva asignación y copia en cada complemento (en comparación con la matriz pura, donde el Length siempre está vinculado al tamaño en la memoria).

Answer 2

Una lista de acceso aleatorio normal generalmente tiene una matriz interna. La implementación .NET List<T> hace esto. Otras implementaciones como LinkedList<T> utilizan cadenas de elementos con referencias en lugar de matrices. Las listas más exóticas pueden usar árboles internamente para ordenar.

La matriz interna en List<T> se inicializa con una longitud corta (creo 4), y si intenta agregar fuera de los límites máximos de la matriz, se expande. Como esto puede llevar mucho tiempo (la matriz debe copiarse), la matriz se duplica en tamaño, es decir, cuando agrega el quinto elemento, la matriz interna se redimensiona a la longitud 8, y así sucesivamente.