Pensamientos de Aztlek

Este escrito te explica como funciona una lista encadenada ¡sin código! solamente con gráficos. Primero te presento la estructura de la lista y después, en cada algoritmo, la especificación y cada uno de los pasos del algoritmo y todo con gráficos (sin una línea de código).

La mejor forma de entender como funcionan las estructuras de datos es haciendo gráficos, pues básicamente las estructuras de datos son grafos y estos son más fáciles de entender en forma visual. Es increíblemente que son pocos los estudiantes que hacen gráficos para entender las estructuras de datos y esto hace que cometan muchos errores.

Pero entremos en materia.

La estructura

Los primero que te voy a mostrar es la estructura (la arquitectura) de una lista encadena en un diagrama de clases UML. Es la siguiente:

Estructura de una lista encadenada

Como puedes ver esta compuesta de dos clases: la lista en si y los nodos de esta lista. La clase Lista tiene una relación a la clase Nodo con primero, esto es, el primer nodo de la lista. ¿Pero donde están los otros nodos de la lista? El truco está en la relación siguiente, que como puedes ver va de la clase Nodo a si misma. Al principio esto puede ser difícil de entender, ¡una clase que está relacionada son si misma! Pero no te preocupes con el siguiente ejemplo se puede ver más claramente.

Ejemplo de lista encadena

La que ves en el gráfico es una lista de nombres. El primer objeto a la izquierda es la Lista y puedes ver que tiene un enlace primero al nodo que tiene por información «Pedro». Hasta aquí esta bien. Pero fíjate que Pedro tiene un enlace al siguiente nodo de la lista, a «Luis», éste es un enlace que va de nodo a nodo, por eso la relación que va de nodo a nodo en al diagrama de clases.

Si vuelves a ver el diagrama de clases puedes ver que las dos clases tiene un parámetro Tipo, este es el tipo de información que contiene cada nodo. En el ejemplo el Tipo es cadena de caracteres. El Tipo es muy importante y permite con la misma estructura tener muchos tipos de lista. Por ejemplo, se podría que Tipo fuera Perro, donde esta es otra clase que contiene el nombre del perro, su edad y su raza, y de esta forma tener una lista de perros. Incluso  ¡Tipo podría ser Lista y tendrías una lista de listas!

Pero volviendo a la tierra y al diagrama de clases puedes ver que la clase Lista tiene varias operaciones, entre esas las de insertar y la de retirar. Y son éstas dos operaciones  las que te explicará a continuación.

La operación insertar

Lo primero que te voy a mostrar es la especificación de la operación, es la siguiente:

Especificación de la operación insertar

Como siempre, si no puedes ver bien el gráfico haz clic en él, y si usas un navegador basado en mozilla, otra vez clic para ampliarlo.

Una especificación de una operación define como debe trabajar esta operación. Esto se logra describiendo la precondición y la postcondición de la operación. Estas dos son como las fotos del antes y el después de la operación (como en el comercial de la chica que usa crema antiarrugas).

Si miras la precondición esta tiene una lista y un nodo suelto (el rojo) que está enlazado por nuevo. Además la lista tiene dos nodos pintados de colores especiales, el verde y al azul (ya, paciencia, ya te digo para que son). En la poscondición el nodo rojo está en la lista entre los nodos verde y azul (para eso eran, para indicar donde se inserta), esto es el nodo  nuevo está insertado en la lista.

La especificación dice que partiendo de la precondición se debe llegar a la poscondición. Y el encargado de hacer esto es el algoritmo.

El algoritmo de insertar

Como te decía atrás el algoritmo debe partir de la precondición, entonces el paso cero del algoritmo es precisamente ese.

Y el siguiente es.

Simplemente hace que el siguiente del nuevo sea el mismo siguiente del nodo verde (o sea, el azul). Después se hace lo siguiente:

El siguiente del verde es el nuevo nodo. Y listo llegamos a la poscondición por lo que al algoritmo ya está completo.

Ahora puedes tomar cada uno de los gráficos y codificarlos en tu lenguaje de objetos favorito.

La operación retirar

La operación retirar tiene la siguiente especificación.

Especificación de la operación retirar

Aparece una lista con tres nodos de colores, verde, rojo y azul. Y el el nodo verde está enlazado con ref, pero es el nodo que está delante de él que se retira (el rojo), quedando el verde y el azul consecutivos.

El algoritmo de retirar

Ahora te voy a mostrar todos los pasos de retirar pero sin muchas explicaciones, si los gráficos están bien hechos esas explicaciones deben sobrar o ser mínimas.

Igual ahora sólo es codificar los gráficos en tu lenguaje a objetos predilecto.

Finalmente

Te vuelvo  reiterar que los gráficos son «imprescindibles» para entender las estructuras de datos: su estructura y sus algoritmos. Puedes usar los diagramas de objetos generales que yo uso aquí, pero no tienen que ser esos necesariamente, lo importante es que uses algún tipo de gráfico.

De otro lado este artículo tiene una segunda parte:Lista encadenada, ¡sin código! con gráficos (segunda parte), en donde te explico otras operaciones de la lista enlazada.