Pensamientos de Aztlek

Este escrito es la segunda parte del artículo Lista encadenada, ¡sin código! con gráficos. En esta parte te explicaré operaciones más avanzadas.

Pero primero recordemos la estructura de la lista encadenada.

Estructura de una lista encadenada

Recordarás que la clase de la izquierda es la lista en si y que la de la derecha es cada uno de los nodos de la lista. La lista tiene una asociación al primer nodo de la lista llamado primero y que el resto de nodos se organizan gracias a la asociación siguiente, y esto es lo que lo hace que sea una lista encadenada.

Pero entremos en materia, las operaciones que te voy a explicar son: insertarPrimero, insertarUltimo e insertarEnSitio.

La operación insertar primero

Esta operación inserta el nuevo nodo al principio de la lista, así la lista esté vacía o no.

La especificación de insertar primero

Veamos la precondición y postcondición de insertarPrimero.

En la precondición puedes ver el nodo que se va a insertar, nuevo, que está de color rojo y la lista en la que he marcado el primero nodo en color verde, este es importante para saber en que posición va a quedar ese nodo.

En las postcondición aparece el nuevo nodo, el rojo, al inicio de la lista, enlazado por primero y el que era antes el primero, el verde, aparece después de él.

Ahora veamos como hacer que esto suceda, esto es, el algoritmo.

El algoritmo de insertar primero

Como en el artículo anterior voy a poner paso a paso al algoritmo mediante diagramas de objetos UML. Y también, como la vez pasada, el paso cero es la precondición.

Recuerda, desde este punto partimos y tenemos que llegar a la postcondición.

Lo primero que hacemos es lo siguiente:

Poner el enlace sig de nuevo, el rojo, a enlazar al primero de la lista, el nodo verde.

Ahora simplemente hacemos lo siguiente:

Ponemos a primero a enlazar al nuevo, el rojo, y listo, llegamos a la postcondición, por lo que todos los pasos del algoritmo están hechos.

La operación insertar último

Ahora te explicaré como hacer una operación que inserte de último un nuevo nodo. Este algoritmo tiene una complejidad adicional que no tenía el anterior, pero en su momento te lo explicaré.

La especificación de insertar último

Lo que hay que hacer en este algoritmo es muy sencillo, es simplemente adicionar al final de la lista el nuevo nodo, el rojo, poniéndolo después del que era el último, el verde.

El algoritmo de insertar último

Comenzamos como siempre con la precondición como el paso cero.

Recuerda que tenemos que llegar a la postcondición.

Ahora hacemos lo siguiente:

Ponemos un nuevo enlace llamado tmp al principio de la lista. Esto es muy sencillo, es simplemente una asignación.

Hasta aquí fácil, veamos el siguiente paso:

Es hacer llegar el tmp al nodo final. ¿Como se hace esto? Con un ciclo, simplemente es un ciclo hasta que el siguiente de tmp sea null. Y realmente esta es la parte fuerte del algoritmo y de hecho es de los pocos algoritmos que vamos a hacer que tengan ciclos.

Veamos el siguiente paso:

Simplemente al siguiente del último, el verde, se le asigna el nuevo, el rojo. Y listo, hemos llegado a la postcondición.

La operación insertar en el sitio

Cuando vimos la operación insertar en la primera parte de esta artículo (Lista encadenada, ¡sin código! con gráficos) insertábamos delante del nodo que estaba referenciado, lo cual no es muy «natural», uno esperaría que se insertara en el sitio que se referencia. Pero como te habrás dado cuenta esto es muy difícil de hacer y muchas de las soluciones implicaban ciclos haciendo muy ineficiente al algoritmo. Pero te voy a presentar una forma de hacer que no implica ciclos, podríamos decir que es un hack.

La especificación de insertar en el sitio

Bueno, las especificación era lo que esperábamos que el nuevo nodo, el rojo, se inserte antes del ref, el azul y después del verde.

El algoritmo de insertar en el sitio

Este algoritmo tiene su complejidad por que para poder poner el nuevo nodo delante del verde necesitaríamos tener un enlace a ese nodo para poner el sig al nuevo. Pero para ello necesitaríamos recorrer toda la lista hasta encontrar al anterior a ref y este sería un algoritmo muy ineficiente, del orden de O(n). Pero para ello vamos a usar un truco, o mejor un hack, pero no voy contarte el final de la película antes de verla.

Veamos el paso cero.

En el siguiente paso pues podemos invocar insertar y ponemos al nuevo, el rojo, delante del ref, el azul.

¿Pero no estamos igual? Ten paciencia, aquí viene el hack, simplemente intercambiamos la información del nodo nuevo, el rojo, con la información de ref, el azul.

Y listo, ¡ya están en orden! Hemos llegado a la postcondición y ¡sin necesidad de usar un ciclo!

Finalmente

Una vez más te reitero que uses gráficos para entender los algoritmos de estructuras de datos y en general todos los algoritmos que involucren algún tipo de grafo. Te puedo garantizar que aprenderás mucho de esta forma y además evitarás muchos errores.

Por otro lado, si quieres seguir aprendiendo sobre estructuras de datos te recomiendo al artículo:Lista doblemente encadenada ¡ahora en versión animada!.