Download - Listas doblemente enlazadas
LISTAS DOBLEMENTE ENLAZADAS
GRUPO 3WILSON CHIACAIZA
JAIRO LEMARENE LASSO
EDISON JACOME
LISTAS DOBLEMENTE ENLAZADAEn las listas doblemente enlazadas, cada elemento contiene
dos punteros aparte del valor almacenado en el elemento. Un puntero apunta al siguiente elemento de la lista y el otro puntero apunta al elemento anterior. La figura 18.6. muestra una lista doblemente enlazada y un nodo de dicha lista.
Las operaciones sobre una lista doblemente enlazada son:Crear listaInsertar nodo al inicio y al FinalEliminar nodo al inicioBuscar o Recorrer
Existe una operación de insertar y eliminar (borrar) en cada dirección. La figura 18.7. muestra el problema de insertar un nodo p a la derecha del nodo actual. Deben asignarse cuatro nuevos enlaces,
En el caso de eliminar (borrar) un nodo de una lista doblemente enlazada es preciso cambiar dos punteros.
Declaración de una lista doblemente enlazada
Una lista doblemente enlazada con valores de tipo int necesita dos punteros y el valor del campo datos. En una estructura se agrupan estos datos del modo siguiente:
typedef int Item;struct unnodo { Int dato; struct unnodo *adelante; struct unnodo *atras; }; typedef struct unnodo Nodo;
Insertar un elemento en una lista doblemente enlazada
El algoritmo empleado para añadir o insertar un elemento en una lista
doble varía dependiendo de la posición en que se desea insertar el
elemento. La posición de inserción puede ser:
En la cabeza (elemento primero) de la lista.En el final de la lista (elemento último).Antes de un elemento especificado.Después de un elemento especificado.
Insertar un nuevo elemento en la cabeza de una lista doble
El proceso de inserción se puede resumir en este algoritmo:
Asignar un nuevo nodo apuntado por nuevo que es una variable puntero que apunta al nuevo nodo que se va a insertar en la lista doble.
Situar el nuevo elemento en el campo dato del nuevo nodo.Hacer que el campo enlace adelante del nuevo nodo apunte
a la cabeza (primer nodo) de la lista original, y que el campo enlace atras del nodo cabeza apunte al nuevo nodo.
Hacer que cabeza (puntero cabeza) apunte al nuevo nodo que se ha creado.
EJEMPLO DE LA OPERACIÓN INSERTAR
CODIGO C
En este momento, la función de insertar un elemento en la lista termina su ejecución, la variable local nuevo desaparece y sólo permanece el puntero de cabeza cabeza que apunta a la nueva lista doblemente enlazada.
Eliminación de un elemento en una lista doblemente enlazada
La operación de eliminar un nodo de una lista doble supone realizar el
enlace de dos nodos, el nodo anterior con el nodo siguiente al que se
desea eliminar, con el puntero adelante, y el nodo siguiente con el anterior, con el puntero atras, y liberar la memoria que ocupa. El algoritmo para eliminar un nodo que contiene un dato es similar al algoritmo de borrado para una lista simple. Ahora la dirección del
nodo anterior se encuentra en el puntero atras del nodo a borrar. Los
pasos a seguir:
Búsqueda del nodo que contiene el dato. Se ha de tener la dirección del nodo a eliminar y la dirección del anterior.
El puntero adelante del nodo anterior tiene que apuntar al puntero adelante del nodo a eliminar, esto en el caso de no ser el nodo cabecera.
El puntero atrás del nodo siguiente a borrar tiene que apuntar al puntero atrás del nodo a eliminar, esto en el caso de no ser el nodo último.
En caso de que el nodo a eliminar sea el primero, cabeza , se modifica cabeza para que tenga la dirección del nodo siguiente .
Por último, se libera la memoria ocupada por el nodo.
Eliminar un elemento3 9 12 NULL
3 9 12 NULL
3 12 9NULL
Se busca el nodo a borrar
Movemos los punteros
Liberamos memoria conFree() o delete
NULL
NULL
NULL
La codificación se presenta en la siguiente función:
BUSCAR O RECORRERPara recorrer una lista procederemos de un modo parecido al que usábamos con las listas abiertas, ahora no necesitamos un puntero auxiliar, pero tenemos que tener en cuenta que Lista no tiene por qué estar en uno de los extremos:Retrocedemos hasta el comienzo de la lista, asignamos a lista
el valor de lista->anterior mientras lista->anterior no sea NULL.
Abriremos un bucle que al menos debe tener una condición, que el índice no sea NULL.
Dentro del bucle asignaremos a lista el valor del nodo siguiente al actual.
Por ejemplo, para mostrar todos los valores de los nodos de una lista, podemos usar el siguiente bucle en C:
Movimiento/búsqueda a través de la lista
3 9 10
proximo
11 12NULL
indice->ant->ant
indice->ant
indice
indice->proximo
indice
NULL
Código Ctypedef struct _nodo { int dato; struct _nodo *siguiente; struct _nodo *anterior; } tipoNodo; typedef tipoNodo *pNodo; typedef tipoNodo *Lista; pNodo = indice; indice = Lista; while(indice->anterior) indice = indice->anterior; while(indice) { printf("%d\n", indice->dato); indice = indice->siguiente; }
GRACIAS POR SU ATENCION