3.4 Listas Doblemente Enlazadas

Una lista doble, ó doblemente ligada es una colección de nodos en la cual cada nodo tiene dos punteros, uno de ellos apuntando a su nodo anterior y otro a su siguiente.

Por medio de estos punteros se podrá avanzar o retroceder a través de la lista, según se tomen las direcciones de uno u otro puntero.

La estructura de un nodo en una lista doble es la siguiente:

Existen dos tipos de listas doblemente ligadas:

• Listas dobles lineales. En este tipo de lista doble, tanto el puntero izquierdo del primer nodo como el derecho del último nodo apuntan a NULL.
• Listas dobles circulares. En este tipo de lista doble, el puntero izquierdo del primer nodo apunta al último nodo de la lista, y el puntero derecho del último nodo apunta al primer nodo de la lista.

En la figura siguiente se muestra un ejemplo de una lista doblemente ligada lineal que almacena números:

En la figura siguiente se muestra un ejemplo de una lista doblemente ligada circular que almacena números:

A continuación mostraremos algunos algoritmos sobre listas enlazadas. Como ya se mencionó, llamaremos Ant al puntero izquierdo y Sig al puntero derecho, también usaremos el apuntador para hacer referencia al primer nodo en la lista, y p para referenciar al nodo presente.