Matrices vs 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 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 una colección de elementos. Se compone de una secuencia de nodos y cada nodo tiene una referencia al siguiente nodo de la secuencia.
En la figura 1, se muestra un fragmento de código que se usa normalmente 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 usando índices de 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, se fija su tamaño. Entonces, si no está seguro del tamaño de la matriz en el momento de la compilación, tendrá que definir una matriz lo suficientemente grande como para estar seguro. Pero, la mayoría de las veces usaremos menos elementos de los que hemos asignado. Por tanto, se desperdicia una cantidad considerable de memoria. Por otro lado, si la "matriz lo suficientemente grande" no es realmente lo suficientemente grande, el programa se bloqueará.
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 eslabones en una cadena. Cada elemento de una lista vinculada 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 vinculada se almacena como el encabezado 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 almacenan una referencia al siguiente elemento. El último elemento tiene un valor nulo en su siguiente campo. Se puede acceder a cualquier elemento de la lista comenzando por el encabezado y siguiendo el siguiente puntero hasta encontrar el elemento requerido.
Aunque las matrices y las listas enlazadas son similares en el sentido de que ambas se utilizan para almacenar una 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 fueran ineficaces 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 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 los 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.
