Trabajo

4.4 Listas Dobles
[pic]
Una lista doble , ó doblemente ligada es una colección de nodos en la cual cada nodo tiene dos punteros, uno de ellosapuntando a su predecesor (li) y otro a su sucesor(ld). Por medio de estos punteros se podrá avanzar o retroceder a través de la lista, según se tomenlas direcciones de uno u otro puntero.
La estructura de un nodo en una lista doble es la siguiente:
[pic]
Existen dos tipos de listas doblementeligadas:
• Listas dobles lineales. En este tipo de lista doble, tanto el puntero izquierdo del primer nodo como el derecho del último nodo apuntana NIL.
• Listas dobles circulares. En este tipo de lista doble, el puntero izquierdo del primer nodo apunta al último nodo de la lista, y elpuntero derecho del último nodo apunta al primer nodo de la lista.
Debido a que las listas dobles circulares son más eficientes, los algoritmos que enesta sección se traten serán sobre listas dobles circulares.
En la figura siguiente se muestra un ejemplo de una lista doblemente ligada lineal quealmacena números:
[pic]
En la figura siguiente se muestra un ejemplo de una lista doblemente ligada circular que almacena números:
[pic]
Acontinuación mostraremos algunos algoritmos sobre listas enlazadas. Como ya se mencionó, llamaremos li al puntero izquierdo y ld al puntero derecho,también usaremos el apuntador top para hacer referencia al primer nodo en la lista, y p para referenciar al nodo presente.

Algoritmo de creación

top