¿Cuál es la diferencia entre matriz y lista?

La matriz es una estructura de almacenamiento continuo

int[] i=new int[3]

i en realidad registra la primera dirección de la matriz, y i[ 1] es en realidad equivalente a sumar un número entero con una dirección de 1 a la dirección de i y luego tomar el valor de esta dirección.

La lista es una estructura de almacenamiento discontinua. Cada nodo de la lista tiene un atributo Siguiente, que registra la dirección de su siguiente nodo.

En otras palabras, cuando queremos encontrar el nodo número 100, todavía necesita comenzar desde el primer nodo y luego realizar 99 operaciones siguientes para encontrar el nodo de la lista [99].

El siguiente código IL se genera al buscar un elemento

Array:

IL_0020: ldloc.0

IL_0021: ldc. i4.3

IL_0022: ldelem.i4

IL_0023: stloc.2.List`1lt; int32gt;::get_Item(int32)

IL_0029: stloc .2

Con estos dos IL, solo espero demostrar que las listas y las matrices tienen diferentes formas de indexar elementos. Por supuesto, no tenemos forma de conocer la implementación de Microsoft del método List get_Item. Pero no es difícil para nosotros imaginarlo:

Dado que la Lista es una lista vinculada, necesito seguir uno por uno, comenzando desde el primer elemento hasta el elemento de índice requerido. Este es un proceso que requiere mucho tiempo.

1. En términos de expansión de espacio:

A la matriz se le debe asignar un tamaño fijo durante la inicialización, como int[] a=new int[3]; int[] a=new int[]; el compilador nos dará un error sin piedad. Sin embargo, la lista no tiene que especificar un tamaño inicial porque el espacio no tiene que ser contiguo.

Resumen 1: Cuando el tamaño es incierto, es mejor usar Lista en lugar de Matriz. Desde una perspectiva operativa:

No entraré en detalles sobre el índice.

Resumen 2: Cuando se requiere una gran cantidad de operaciones de búsqueda, lo mejor es utilizar Array.

Para las operaciones de inserción (eliminación), muchas personas analizan el tiempo de inserción (eliminación) y dicen que List es mejor que Array. Creo que esto no es razonable.

Una explicación más razonable debe analizarse desde dos perspectivas (tomando la inserción como ejemplo):

lt 1gt; p> Para Array, hay dos conjuntos de soluciones:

A. Utilice una nueva matriz con N 1 elementos para redistribuir el valor del proceso. La complejidad temporal de un bucle for es O (n).

B. Para operar en la matriz original, primero debe reservar espacio para la matriz, lo cual es una tarea difícil. Y la complejidad que requiere mucho tiempo para mover sus elementos posteriores aún no es O (n).

Para List, mucha gente dice que su complejidad es O(1). En realidad, esto no es razonable, porque es fácil insertar elementos de Lista, pero insertarlos en una posición específica requiere un proceso de búsqueda con una complejidad temporal de O (n).

Pero no basta con considerar la complejidad del tiempo, también debemos considerar la situación general. Si se utiliza una nueva matriz, no sólo se desperdiciará nuevo espacio, sino que también se requerirán N 1 procesos de asignación iterativos. Si no usamos una nueva matriz, sería demasiado engorroso reservar espacio, por lo que, en general, es mejor usar una Lista.

lt;2gt; Dado el nodo anterior, inserte un elemento después de él.

Quiero decir, no solo da el valor del nodo anterior, sino también el del siguiente. Déjame decirlo sin rodeos: List es genial. Pero en realidad, la probabilidad de que esto suceda es casi nula.

Entonces, resumen 3: cuando se requieren operaciones frecuentes de inserción y eliminación, es mejor usar Lista en lugar de Matriz.

Otra adición menos importante es que List desperdicia más espacio que Array porque necesita almacenar la dirección del siguiente nodo.

En otras palabras, aunque el uso del paradigma fuertemente tipado listlt;Tgt; puede ahorrar tiempo al empaquetar y desempaquetar, la velocidad de las consultas será un gran problema.

En aplicaciones prácticas, cuando los cambios son pequeños y el número de consultas es frecuente, debemos considerar situaciones distintas a listlt;

Por supuesto, la velocidad de consulta es determinada; value En términos de velocidad, Hashtable o Dictionary son los más rápidos. Por supuesto, son completamente diferentes de lo que estamos comentando y sus estructuras no son comparables. Después de todo, las matrices ahorran espacio, mientras que las tablas hash están procesadas, sacrificando espacio por velocidad.