Wednesday, August 07, 2013

El lenguaje es una lista ligada


Una de las estructuras de datos que se aprenden en los cursos correspondientes de programación son las listas ligadas. Para entender de qué se trata esto, imaginemos que tenemos una serie de números que deben enlazarse en un orden unos con otros. Por ejemplo, en la siguiente imagen:



Aquí, por la razón particular que sea, el número 12 se enlaza al 99 éste al 37. El 37 se enlaza a un final que en general se denomina NIL, es decir, a un punto en donde ya no se apunta a ninguna parte.

Las listas ligadas nos permiten generar nuevos elementos sin alterar estos, sino que lo que ahcemos es generar un nuevo apuntador al siguiente número y así sucesivamente. Este es un clásico ejemplo de una estructura dinámica.

Cuando hacemos, por ejemplo, cálculos aritméticos en una computadora, normalmente el tamaño de palabra en números reales, definidos por los lenguajes de programación es suficiente para los usos cotidianos. Sin embargo, cuando queremos hacer, por ejemplo, un programa que permita hacer cálculos con una precisión mucho mayor (a unos 4 mil millones), entonces tenemos un problema, porque el tamaño definido para los números reales no nos da la capacidad adecuada. Es aquí donde se puede generar una lista dinámica de números, de dígitos, para generar un número tan grande como se deseé. Si queremos hacer cálculos sobre ese número, tendremos que finalmente, enseñarle a la computadora a hacer las operaciones de nodo en nodo y llevar los valores que se acarrean cuando estamos, por ejemplo, haciendo una larga suma.

Las listas ligadas (también llamadas, enlazadas), nos permiten de alguna manera trabajar con conjuntos de datos sin necesidad de tener que usar arreglos en una dimensión. De hecho, un problema con los arreglos es -en principio- que son estructuras de datos fijas, que además, no se pueden generar fácilmente en un programa de computadora, pues muchas veces tenemos que decirle a nuestro programa, a priori, el tamaño del arreglo. Dicho de otra manera, son estructuras estáticas y aunque son muy útiles en muchos casos, tienen sus propios inconvenientes.

Existen listas doblemente ligadas, es decir, cada elemento tiene dos ligas, una al siguiente elemento y otra al anterior. Un caso donde se puede usar esta idea es cuando se programa, por ejemplo, un sistema para desplegar partidas de ajedrez. Lo que se hace es leer la partida y guardar cada posición con dos apuntadores, uno a la posición anterior y otro a la posición siguiente. Eso permite entonces hacer un programa que simplemente nos permita movernos de jugada en jugadfa, hacia adelnate o hacia atrás, desplegando el tablero correspondiente.



Una de las ventajas de las listas ligadas es que permite, por ejemplo, eliminar elementos fácilmente, como se ve en la siguiente figura.



Aquí un elemento es dado de baja, lo borramos... ¿cómo? simplemente quitamos sus enlaces a la lista y ya no lo tenemos. Sin embargo, esto tiene un inconveniente. El elemento sigue en memoria, inaccesible, y utiliza memoria que no podemos usar porque no lo hemos literalmente borrado, solamente lo dimos de baja de nuestra lista ligada. Aquí tenemos que lidiar con esta dificultad y desde luego, hay mecanismos, como el del recolectro de basura, pero de eso hablaremos en otro momento.

Lo que he estado pensando es que el idioma, los lenguajes que hablamos los seres humanos son en realidad listas ligadas. Un ejemplo claro es la poesía. Quien se aprende un poema lo que hace es acordarse de qué palabra sigue a la otra. Así, si lo vemos como un problema de cómputo, podremos ver que se trata de una lista simplemente ligada. No lo es doblemente porque quien se aprende una poesía no la puede decir al revés. Solamente se dice de una manera.

Yendo más lejos aún entonces, nuestros cerebros han acomodado las palabras de manera tal que tienen asociado un apuntador *un puntero dirían los españoles) a una siguiente palabra. Podría ser, sin embargo, que cada palabra tuviese apuntadores no a una sola palabra siguiente (como en el caso de la poesía), sino a todo un conjunto de palabras que pueden ser ligadas directamente.

Y si vamos aún más lejos, la ortografía parece ser también un asunto de listas ligadas simples. Es claro que en muchos casos una letra sigue a la otra y sin embargo, hay unas que están vetadas. Por ejemplo:

e - > n - > b - > i - > a - > r

Podría considerarse una lista ligada ilegal o inválida, pues sabemos que después de una "n" nunca va una "b".

Quisiera pensar que el cerebro tiene un mecanismo que permite crear a través de las neuronas estas redes de listas ligadas. La pregunta entonces es: ¿podríamos desencriptar esta maraña de redes de neuronas como listas ligadas y ver cómo el cerebro está organizando la información? Por el momento me parece que estamos lejos de ello, pero bueno, es una reflexión nada más.

2 comments:

Edgar Castillo said...

Si el lenguaje es una lista ligada, la pregunta obligada es Cómo es el algoritmo para poner los apuntadores entre una letra y otra? y Yo me atrevería a pensar que más que ser una lista ligada simple o doble, es una malla con n-ligas

Malopezmx said...

Muy interesante este concepto, aplaudo la originalidad de la idea. Da para divagar, mirando al techo, en esas tardes en las que no hay mucho que hacer. Pudieran llegarse a resultados originales.