implementar lista vinculada utilizando matriz - ventajas y desventajas

Question

Sé cómo implementar la lista vinculada usando una matriz. Por ejemplo definimos una estructura como sigue:

struct Node{ 
    int data; 
    int link; 
} 

tiendas de "datos" de la información y la almacena "link" el índice de la matriz de nodo siguiente.

¿Alguien me puede decir cuál es la ventaja y la desventaja de implementar una lista vinculada usando un conjunto en comparación con la lista vinculada "ordinaria"? Cualquier sugerencia será apreciada.

Answer 1

Si respalda una lista vinculada con una matriz, terminará con las desventajas de ambos. En consecuencia, esta no es probablemente una muy buena forma de implementarla.

Algunos inconvenientes inmediatos:

1. Tendrá espacio muerto en la matriz (las entradas que no se utilizan actualmente para los artículos) ocupando la memoria
2. Vas a tener que llevar un registro de los libres entradas: después de algunas inserciones y eliminaciones, estas entradas gratuitas podrían estar en cualquier lugar.
3. El uso de una matriz impondrá un límite superior en el tamaño de la lista vinculada.

supongo algunas ventajas son:

1. Si estás en un sistema de 64 bits, los "punteros" se ocupan menos espacio (aunque el espacio adicional requerido por las entradas gratuitas probablemente mayor que esta ventaja)
2. Puede serializar la matriz en el disco y leerla de nuevo con una llamada mmap() fácilmente. Sin embargo, sería mejor utilizar algún tipo de búfer de protocolo para la portabilidad.
3. Puede hacer algunas garantías acerca de que los elementos de la matriz estén cerca uno del otro en la memoria.

Answer 2

Alguien puede decirme cuál es la ventaja y desventaja de ejecución de lista enlazada utilizando matriz en comparación con lista enlazada "ordinario"?

listas enlazadas tienen la siguiente complejidad:

• Contras x xs: O (1)
• append nm: O (n)
• índice i xs: O (n)

si su represe ntation utiliza una estricta serie, contiguo, que tendrá diferente complejidad:

• contras requerirán copiar la matriz de edad: O (n)
• append requerirá copia de ambas matrices en un nuevo espacio contiguo: O (n + m)
• índice puede ser implementado como acceso a una matriz: O (1)

es decir, una API lista enlazada implementado en plazo s de arreglos se comportará como una matriz.

Puede mitigar esto de alguna manera mediante el uso de una lista vinculada o un árbol de matrices estrictas, lo que conduce a cuerdas o árboles de dedos o secuencias perezosas.

Answer 3

pila en implemento de dos vías. primero en el uso de la matriz y el segundo está utilizando la lista vinculada.

algunas desventajas en el uso de la matriz, entonces la mayoría de los programadores utilizan la lista vinculada en la implementación de la pila.

primero es la pila que utiliza primero la lista vinculada no declara el tamaño de pila y el almacén de datos no limitado en la pila. el segundo es la lista vinculada en el ensayo del puntero para declararlo y usarlo.

uso de un solo puntero en la lista vinculada. se llama puntero superior.

stack is lifo method use. pero algunas desventajas en la implementación del programa de listas vinculadas.

La mayoría de los programadores usan la implementación de la pila usando la lista de Me gusta.

Answer 4

Usando aplicación matriz, puede tener acceso secuencial & más rápido a los nodos de la lista, por el contrario, Si se implementa la lista vinculado el uso de punteros, se puede tener acceso aleatorio a los nodos. La implementación de matriz es útil cuando se trata de no. De elementos debido a que el redimensionamiento de una matriz es costoso en lo que respecta al rendimiento, ya que si se le pide que inserte/elimine nodos de la mitad de la lista, debe desplazar todos los nodos de forma consecutiva. Contrariamente a esto, debe usar la implementación del puntero cuando no sepa que no. de nodos que desee, ya que dicha lista puede crecer/contraerse de manera eficiente & no es necesario cambiar ninguno de los nodos, se puede hacer simplemente desreferenciando & haciendo referencia a los punteros.