Diferencia entre matrices y listas vinculadas

Matrices vs listas vinculadas

Las matrices son la estructura de datos más utilizada para almacenar la recopilación de elementos. La mayoría de los lenguajes de programación proporcionan métodos para declarar fácilmente matrices y elementos de acceso en las matrices. La lista vinculada, la lista con un solo enlace individual, también es una estructura de datos que se puede utilizar para almacenar la recopilación de elementos. Está compuesto por una secuencia de nodos y cada nodo tiene una referencia al siguiente nodo en la secuencia.

Se muestra en la Figura 1, se utiliza un código que se usa típicamente para declarar y asignar valores a una matriz. La Figura 2 muestra cómo se vería una matriz en la memoria.

El código anterior define una matriz que puede almacenar 5 enteros y se accede a ellos utilizando índices 0 a 4. Una propiedad importante de una matriz es que la matriz completa se asigna como un solo bloque de memoria y cada elemento obtiene su propio espacio en la matriz. Una vez que se define una matriz, su tamaño es fijo. Entonces, si no está seguro del tamaño de la matriz en el momento de la compilación, tendría que definir una matriz lo suficientemente grande como para estar en el lado seguro. Pero, la mayoría de las veces en realidad vamos a usar menos número de elementos de los que hemos asignado. Entonces, una cantidad considerable de memoria en realidad se desperdicia. Por otro lado, si la "matriz lo suficientemente grande" no es realmente lo suficientemente grande, el programa se bloquearía.

Una lista vinculada asigna memoria a sus elementos por separado en su propio bloque de memoria y la estructura general se obtiene vinculando estos elementos como enlaces en una cadena. Cada elemento en una lista vinculada tiene dos campos como se muestra en la Figura 3. El campo de datos contiene los datos reales almacenados y el campo siguiente contiene la referencia al siguiente elemento en la cadena. El primer elemento de la lista vinculada se almacena como el jefe de la lista vinculada.

Figura 3: Elemento de una lista vinculada

La Figura 4 muestra una lista vinculada con tres elementos. Cada elemento almacena sus datos y todos los elementos, excepto el último, almacene una referencia al siguiente elemento. El último elemento contiene un valor nulo en su próximo campo. Se puede acceder a cualquier elemento en la lista comenzando en la cabeza y siguiendo el siguiente puntero hasta que cumpla con el elemento requerido.

Aunque las matrices y las listas vinculadas son similares en el sentido de que ambos se utilizan para almacenar la recopilación de elementos, incurren en diferencias debido a las estrategias que usan para asignar memoria a sus elementos. Las matrices asignan memoria a todos sus elementos como un solo bloque y el tamaño de la matriz debe determinarse en tiempo de ejecución. Esto haría que las matrices sean ineficientes en situaciones en las que no conoce el tamaño de la matriz en el momento de la compilación. Dado que una lista vinculada asigna memoria a sus elementos por separado, sería muy eficiente en situaciones en las que no conoce el tamaño de la lista en el momento de la compilación. Declaración y acceso a elementos en una lista vinculada no sería sencillo en comparación con la forma en que accede directamente a los elementos en una matriz utilizando sus índices.