EL ARTE DEL MAQUILLAJE

LISTA DOBLEMENTE ENLAZADA

Si disponemos de nodos dotados de dos campos de enlace, podemos emplearlos para construir lo que se denomina una lista doblemente enlazada. Estas listas se caracterizan porque cada nodo contiene la dirección del nodo siguiente dentro de la lista, y la dirección del nodo anterior dentro de la misma.

El primer nodo de la lista tiene el valor NULL en el campo que señalaría el nodo anterior; de este modo, es posible reconocerlo.

Resulta cómodo disponer de un puntero que señale a este nodo. Téngase en cuenta la necesidad de actualizarlo cuando se realicen acciones que exijan cambiar su valor para mantener la integridad de la lista.

El último nodo de la lista contiene el valor NULL en el campo que señalaría el nodo siguiente. Esto permite reconocerlo, aunque también es frecuente emplear un puntero de nodo final con esta intención.

Resulta cómodo disponer de un puntero que señale a este nodo. Téngase en cuenta la necesidad de actualizarlo cuando se realicen acciones que exijan cambiar su valor para mantener la integridad de la lista.

El resultado final es una lista doblemente enlazada, que presenta un aspecto similar al que puede verse en la figura.

La característica más sobresaliente de este tipo de estructura no lineal es que cada nodo contiene la información necesaria para acceder tanto al elemento anterior como al elemento siguiente. El mayor coste de memoria se ve compensado ampliamente por la gran facilidad que ofrecen estas estructuras a la hora de añadir y eliminar nodos, al contrario de lo que sucede en las listas simplemente enlazadas. Inserción y eliminación de nodos.

Este proceso es completamente análogo al estudiado en la sección anterior, relativa a listas simplemente enlazadas. De hecho, el manejo de listas doblemente enlazadas resulta más sencillo, puesto que basta localizar un nodo para poder eliminarlo, o añadir un nodo delante o detrás de él, al contar en todo momento con la dirección del nodo anterior.

Proceso de inserción:

Las imágenes siguientes describen la situación de una lista doblemente enlazada al realizar distintas operaciones.

Inserción de un nodo al principio de la lista

Como puede observarse, el puntero de nodo siguiente del nuevo nodo pasa a tomar el valor de ppio; el puntero de nodo anterior del nodo señalado por ppio deja de ser NULL y pasa a apuntar al nuevo nodo; finalmente, ppio pasa a apuntar al nuevo nodo.

Inserción de un nodo al final de la lista

En este caso, es preciso hacer que el puntero de nodo siguiente del nodo señalado por fin apunte al nuevo nodo. A continuación, se hace que el puntero de nodo anterior del nodo nuevo apunte al nodo señalado por fin. Por último, se hace que fin apunte al nuevo nodo.

Inserción de un nodo en posición intermedia.

La inserción en posición intermedia se hace a partir del puntero del nodo tras el cual se quiere insertar. El manejo de punteros es como sigue:

1. El nodo nuevo debe apuntar al nodo siguiente.

2. El nodo siguiente debe apuntar al nodo nuevo.

3. El nodo anterior debe apuntar al nodo nuevo.

4. El nodo nuevo debe apuntar al nodo anterior.

Se observará la mayor comodidad al disponer del puntero de nodo anterior y de nodo siguiente.

Proceso de eliminación:

De nuevo se trata de

...