Diferencia entre matrices y listas enlazadas

Arrays vs Listas Vinculadas

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

En la figura 1, se muestra un fragmento de código que normalmente se utiliza 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 mediante los índices 0 a 4. Una propiedad importante de una matriz es que toda la matriz 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 sobre el 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 vamos a usar menos elementos de los que hemos asignado. Así que una cantidad considerable de memoria se desperdicia realmente. Por otro lado, si la "matriz lo suficientemente grande" no es realmente lo suficientemente grande, el programa se bloquearía.

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

Figura 3: Elemento de una lista enlazada

La figura 4 muestra una lista enlazada con tres elementos. Cada elemento almacena sus datos y todos los elementos excepto el último almacenan una referencia al siguiente elemento. El último elemento mantiene un valor nulo en su siguiente campo. Se puede acceder a cualquier elemento de la lista comenzando en la cabecera y siguiendo el siguiente puntero hasta que cumpla con el elemento requerido.

Aunque las matrices y las listas enlazadas son similares en el sentido de que ambas se utilizan para almacenar la colección de elementos, incurren en diferencias debido a las estrategias que utilizan 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 se conoce el tamaño de la matriz en el momento de la compilación. Dado que una lista vinculada asigna la memoria a sus elementos por separado, sería mucho más eficiente en situaciones en las que no se sabe el tamaño de la lista en el momento de la compilación. La declaración y el acceso a los elementos de una lista enlazada no serían sencillos en comparación con la forma en que se accede directamente a los elementos de una matriz utilizando sus índices..