Matrices frente a listas enlazadas
Las matrices son la estructura de datos más utilizada para almacenar una colección de elementos. La mayoría de los lenguajes de programación proporcionan métodos para declarar arreglos fácilmente y acceder a elementos en los arreglos. La lista enlazada, más precisamente la lista enlazada individualmente, también es una estructura de datos que se puede usar para almacenar una colección de elementos. Se compone de 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 usa 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 números 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 tiene 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, deberá definir una matriz lo suficientemente grande para estar seguro. Pero, la mayoría de las veces vamos a utilizar menos elementos de los que hemos asignado. Por lo tanto, se desperdicia una cantidad considerable de memoria. Por otro lado, si la "matriz lo suficientemente grande" no es lo suficientemente grande, el programa fallará.
Una lista enlazada asigna memoria a sus elementos por separado en su propio bloque de memoria y la estructura general se obtiene enlazando estos elementos como eslabones en una cadena. Cada elemento de 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.
| datos | siguiente |
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 contiene un valor nulo en su siguiente campo. Se puede acceder a cualquier elemento de la lista comenzando en el encabezado y siguiendo el siguiente puntero hasta que encuentre el elemento requerido.
Aunque las matrices y las listas enlazadas son similares en el sentido de que ambas se usan para almacenar una colección de elementos, tienen 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 fueran 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 enlazada asigna memoria a sus elementos por separado, sería mucho más eficiente en situaciones en las que no conoce el tamaño de la lista en el momento de la compilación. La declaración y el acceso a elementos en una lista enlazada no serían sencillos en comparación con la forma en que accede directamente a los elementos en una matriz utilizando sus índices.
