Listas doblemente enlazadas.

   Aunque una lista enlazada circular tiene ventajas sobre una lista simplemente enlazada (vea la entrada Listas circulares), también tiene algunas desventajas:

• No es posible recorrer la lista enlazada circular hacia atrás (o hacia la izquierda); es decir, sólo puede recorrerse en un sentido.
• Dada una referencia a un nodo determinado de la lista enlazada circular, no es posible eliminar dicho nodo utilizando únicamente dicha referencia (¿Por qué?).

   En este sentido, una estructura de datos conveniente para subsanar dichas desventajas es precisamente, la lista doblemente enlazada.

Definición, primitivas y representación.

   Una lista doblemente enlazada es una colección lineal de nodos auto referidos en donde cada nodo tiene dos referencias:

1. Una referencia al sucesor del nodo actual (siguiente).
2. Una referencia al antecesor del nodo actual (anterior).

   La representación de una lista doblemente enlazada se muestra en la figura (a). Observe cómo al igual que en una lista enlazada, una lista doblemente enlazada puede ser también doblemente enlazada circular (figura (b)). Esta última, sigue también las mismas consideraciones que se hicieron en su momento para una lista enlazada circular.

(a) Abstracción de una lista doblemente enlazada.

(b) Abstracción de una lista doblemente enlazada circular.

   Adicionalmente, las operaciones primitivas para una lista doblemente enlazada son exactamente las mismas que para una lista simplemente enlazada, por lo que no se repetirán aquí.

   Por otro lado, los diagramas de clases UML para los lenguajes Java y C++ de una lista doblemente enlazada se presentan a continuación. Los diagramas complementan la definición de la estructura de datos a través de su correspondiente diseño de clases:

Diagrama de clases UML para una lista doblemente enlazada (Java).

 

Diagrama de clases UML para una lista doblemente enlazada (C++).

 

    Por ultimo, note que dichos diagramas de clases son sustancialmente distintos de los que en general se han utilizado hasta ahora para el diseño de las anteriores estructuras de datos y que, exceptuando la clases ExcepcionEDVacia (excepcion_ED_vacia), tanto las clases ListaDoble (lista_doble) como las clases NodoDobleG (Nodo_doble) han sufrido cambios significativos. Consulte la sección de ejercicios correspondiente para obtener más detalles al respecto.