Pensamientos de Aztlek

En este escrito te explico lo básico de una lista doblemente encadenada: su estructura y sus dos operaciones principales: insertar y retirar,  y en cada una éstas la precondición, la postcondición y el algoritmo. Al igual que en Lista encadenada lo vemos con gráficos para que lo puedas entender más fácilmente.

Pero entremos en materia de una vez. Lo primero que te voy a mostrar es la estructura.

Estructura

Estructura de la lista Doblemente Encadenada

Como vez está representada en un diagrama de clases UML.  Es muy parecida a la del artículo de Lista encadenada, pero la diferencia significativa es que la clase Nodo tienen dos asociaciones, donde antes había sólo una, la nueva es llamada ant y es precisamente ésta lo que la hace una lista doblemente encadenada. Y es ésta asociación la que sirve para recorrer la lista en orden inverso.

Pero comencemos a ver la operaciones, en este escrito soĺo veremos dos: insertar y retirar. Basado en ellas puedes desarrollar las otras operaciones.

Operación insertar

Especificación de la operación insertar

Para no decir mucha palabrería veamos directamente la especificación, esto es el encabezado,  la precondición y la postcondición de la operación insertar.

Como puedes ver tenemos tres entradas: la lista, una referencia ref que indica donde se debe insertar y una referencia al nuevo nodo. Como se ve en la postcondición el nuevo nodo debe quedar al frente de la nueva referencia.

Algoritmo de la operación insertar

El paso cero del algoritmo es la misma precondición.

Este paso no tiene ningún código (es la precondición y el paso cero).
El siguiente es,

Que simplemente pone el siguiente de nuevo a referenciar al siguiente de ref. Fíjate que debajo del diagrama e puesto la sentencia equivalente en java, que además está coloreada para que te puedas guiarte más fácilmente.

Ahora pusimos al anterior de nuevo a reverenciar a ref.

En la anterior ilustración pusimos el anterior del siguiente de ref a referenciar a nuevo. Cuando implementes el código no se te olvide verificar que ref, el sig de ref y el ant no sean nulos.

Y finalmente ponemos el siguiente de ref a referenciar nuevo y listo, hemos llegado a la postcondición.

He elaborado una animación con cada uno de estos paso y es posible que con ella entiendas más. Como siempre si no la puedes ver bien haz clic sobre ella y podrás verla más grande y si la quieres ver aún más grande  haz clic otra vez.

Animación del algoritmo de insertar en una lista doblemente encadenada.

 Operación retirar

Especificación de la operación retirar

Lo que tiene que hacer esta operación es muy sencillo: consiste en retirar el nodo referenciado por ref de la lista. Mira que no se borra, simplemente se retira de la lista, pero si le quitas todas las referencia al nodo entonces borrarías el nodo.

Ahora te mostraré el desarrollo de  esta operación, paso por paso y con gráficos.

Algoritmo de la operación retirar

El paso cero, como siempre, es la precondición.

Recuerda que la precondición no tiene código asociado, por eso no te lo muestro. Pero veamos ahora el verdadero primer paso del algoritmo.

Lo que se hizo en este paso redireccionar el siguiente del anterior de ref a el siguiente de ref (se entiende más en el gráfico)

En el anterior lo que hicimos fue la operación simétrica a la anterior, mira que en este punto el nodo nuevo ya casi está desenlazado de la lista.

Lo que acabo de hacer fue poner el siguiente y al anterior de ref a null, para finalmente independizarlo de la lista. Esta operación no es necesaria, pero es una buena práctica poner a null las referencias que no se están usando.

Finalmente se retorna ref. Y listo, llegamos a la postcondición.

Ahora la versión animada.

Animación de la operación retirar en una lista doblemente encadenada

Finalmente

Como ya te dije en otras ocasiones (¿Como funcionan las referencias en Java? y Lista encadenada) el secreto para entender las estructuras con referencias son los dibujos. Por lo que te recomiendo encarecidamente, ¡haz dibujos!