Matrices y listas enlazadas

Una matriz es una estructura de datos básica. ¿Mesa lineal? Una estructura de datos que utiliza un conjunto contiguo de espacios de memoria para almacenar un conjunto de datos del mismo tipo. (Pero en JavaScript no es un conjunto contiguo de espacios de memoria y es posible almacenar diferentes tipos de valores en una matriz. Pero aún tenemos que seguir las buenas prácticas y no hacer eso, la mayoría de los lenguajes no tienen esta capacidad. ).

Análisis de sustantivos: 1. Tabla lineal: Una tabla lineal tiene la misma estructura que los datos dispuestos en una fila. Los datos de cada tabla lineal tienen como máximo dos direcciones. De hecho, además de las matrices, las listas vinculadas, las colas y las pilas también son estructuras de listas lineales. El concepto opuesto son las tablas no lineales, como árboles binarios, montones y gráficos. Se llama no lineal porque en una tabla no lineal no existe una relación contextual simple entre los datos.

? 2. ¿Espacio de memoria continuo? y el mismo tipo de datos. Es por estas dos limitaciones que se puede acceder a él de forma aleatoria. Pero existen ventajas y desventajas. ¿Estas dos restricciones también dificultan muchas operaciones en matrices? Ineficiencia Por ejemplo, si desea eliminar o insertar un dato en una matriz, se requiere mucho movimiento de datos para garantizar la continuidad.

? En comparación con una matriz, una lista vinculada es una estructura de datos un poco más compleja. Los elementos de una lista vinculada se pueden almacenar en cualquier lugar de la memoria (a diferencia de las matrices, que requieren espacio de memoria contiguo). Cada elemento de la lista enlazada se almacena. La dirección del siguiente elemento se utiliza para concatenar un conjunto de bloques de memoria dispersos a través de "punteros", conectando así una serie de direcciones de memoria aleatorias.

Varias estructuras comunes de listas enlazadas: lista enlazada simple, lista enlazada doble y lista enlazada circular.

? Un nodo en una lista enlazada única debe tener dos atributos: ¿val? Entonces qué. Entonces

lista individualmente enlazada

? Contiene dos campos, un campo de información y un campo de puntero. El enlace apunta al siguiente nodo de la lista y el último nodo apunta al valor nulo.

¿Lista doblemente enlazada

? Cada nodo tiene dos conexiones: una apunta al nodo anterior (cuando esta "conexión" es la primera "conexión", apunta a un valor nulo o una lista vacía) la otra apunta al siguiente nodo (cuando esta "conexión"); es Cuando el último está "conectado", apunta a un valor nulo o una lista vacía)

Lista circular enlazada

El primer nodo y el último nodo están conectados entre sí.

? Para mantener la continuidad de los datos en la memoria, estas dos operaciones, inserción y eliminación, serían ineficientes.

Siempre que insertamos un dato en la k-ésima posición de la matriz, para dejar la k-ésima posición vacía, necesitamos desplazar todos los datos después de k uno. Entonces la complejidad del tiempo promedio es O (n).

De manera similar, si queremos eliminar los datos en la posición k, necesitamos mover los datos para la continuidad de la memoria; de lo contrario, aparecerán agujeros en el medio y la memoria será discontinua, por lo que la complejidad del tiempo promedio es también O(n) .

? De hecho, en algunos casos especiales, no tenemos que buscar la continuidad de los datos en la matriz. Si realizamos varias operaciones de eliminación juntas, ¿mejorará mucho la eficiencia de la eliminación? Sigamos con el ejemplo. Se almacenan ocho elementos en la matriz A [10]: A, B, C, D, E, F, G y h. Ahora, eliminaremos los tres elementos A, B y C en secuencia.

? Para evitar que los datos de D, E, F, G y H se muevan tres veces, puede registrar los datos eliminados primero. Cada eliminación no es realmente datos en movimiento, ¿solo? Los datos de registro se han eliminado. Cuando la matriz no tenga más espacio para almacenar datos, activaremos la operación de eliminación real, lo que reduce en gran medida el movimiento de datos causado por la operación de eliminación.

? Si hay muchas eliminaciones e inserciones en la situación real, para mejorar la complejidad temporal de las eliminaciones e inserciones, podemos utilizar listas vinculadas.

Al insertar o eliminar una lista vinculada, no necesitamos mover nodos para mantener la continuidad de la memoria, porque el espacio de almacenamiento de la lista vinculada en sí es discontinuo. Por tanto, insertar y eliminar datos en una lista vinculada es muy rápido.

Pero si desea acceder aleatoriamente al k-ésimo elemento, la eficiencia de la lista vinculada no es tan buena como la de la matriz.

Debido a que los datos en la lista vinculada no se almacenan continuamente, la fórmula de direccionamiento no se puede pasar en función de la primera dirección y el subíndice como una matriz. La dirección de memoria correspondiente se puede calcular directamente, pero debe recorrerse nodo por nodo según el puntero hasta encontrar el nodo correspondiente, por lo que la complejidad del tiempo es O (n).

Resumen: las listas enlazadas son adecuadas para inserción y eliminación, y la complejidad temporal es O (1); las matrices admiten acceso aleatorio, y la complejidad temporal del acceso aleatorio por subíndice es O (1); ?

? 1. Las listas enlazadas son diferentes de las matrices. Las matrices requieren espacio de memoria contiguo, pero las listas vinculadas no. Utiliza un conjunto de bloques de memoria dispersos y concatenados mediante "punteros".

Nota: ¿En serio? Una matriz en JavaScript es un objeto de lista cuyo prototipo proporciona operaciones relacionadas para atravesar y modificar elementos. La longitud y los tipos de elementos de las matrices de JavaScript no son fijos. ¿Porque la longitud de la matriz puede cambiar en cualquier momento y sus datos también pueden estar en la memoria? Discontinuas, por lo tanto, las matrices de JavaScript no son necesariamente densas, dependiendo de cómo se utilicen. En JS, las matrices se implementan mediante mapas hash o diccionarios, por lo que no son contiguos. En términos generales, estas características de las matrices son cómodas de usar, pero si no son adecuadas para su caso de uso específico, puede considerar usar matrices escritas. ¿De qué estamos hablando? Matrices en JavaScript.

? 2. Los elementos de la matriz están todos juntos; los elementos de la lista vinculada están separados, donde cada elemento almacena la dirección del siguiente elemento.

? 3. Las matrices se pueden leer muy rápidamente; las listas vinculadas se pueden insertar y eliminar rápidamente.

Resumen: ¿Qué pasa si lo necesitas con frecuencia? ¿Reponer? ¿aún? ¿borrar? Los nodos y las listas enlazadas pueden ser una buena opción.

Si necesita acceder con frecuencia a elementos por índice, una matriz puede ser una mejor opción que una lista vinculada.