Listaligadajava

Instituto Tecnológico de
Durango











Lic. en Informática

“Estructura de Datos”
Ing. Carlos Eduardo Calderón Pérez

Listas Doblemente Enlazadas

Cepeda Chavez Saida Maricela
De la Hoya Tovar Blanca Estela
Ovalle Garcia Cristian
Zamudio Arroyo Chistian Alejandro







-LISTAS DOBLEMENTE LIGADAS-

1.-¿Qué son las listas doblemente enlazadas? y ¿Cuál es su importancia?
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 predecesor (li) y otro a su sucesor (ld).
La estructura de un nodo en una lista doble es la siguiente:
Ant Dato Sig |

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

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 NIL o NULL.
En la figura siguiente se muestra un ejemplo de una lista doblemente ligada lineal que almacena letras:• 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 circular que almacena números:

Importancia:
Nos permite almacenar datos de una forma organizada
Es una estructuraTDA dinámica
cada nodo de la lista doblemente enlazada contiene dos punteros, de forma que uno apunta al siguiente nodo y el otro al predecesor (permite que se pueda recorrer la lista en ambos sentidos).
Operaciones sobre la lista doblemente enlazadas
A. Inicialización
* Esta operación debe ser hecha antes de cualquier otra operación sobre la lista.
* Esta inicializa el punteroinicio y el puntero fin con el puntero NULL, y el tamaño con el valor 0.
B. Inserción de un elemento en la lista

A continuación el algoritmo de inserción y registro de los elementos:
* declaración del elemento a insertar
* asignación de la memoria para el nuevo elemento
* rellenar el contenido del campo de datos
* actualizar los punteros hacia el elemento anterior y elelemento siguiente
* actualizar los punteros hacia el 1er y último elemento si es necesario.
* Caso particular: en una lista con un solo elemento, el primero es al mismo tiempo el último.
* Actualizar el tamaño de la lista

Para añadir un elemento a la lista hay varias situaciones:
* 1. Inserción en una lista vacía
* 2. Inserción al inicio de la lista
* 3. Inserciónal final de la lista
* 4. Inserción antes de un elemento
* 5. Inserción después de un elemento
1. Inserción en una lista vacía

La función devuelve -1 en caso de error, si no devuelve 0.

Etapas:
* asignación de memoria para el nuevo elemento
* rellenar el campo de datos del nuevo elemento
* el puntero anterior del nuevo elemento apuntará hacia NULL (ya que lainserción es hecha en una lista vacía utilizamos la dirección del puntero inicio que vale NULL)
* el puntero siguiente del nuevo elemento apuntará hacia NULL (ya que la inserción es hecha en una lista vacía se utiliza la dirección del puntero fin que vale NULL)
* los punteros inicio y fin apuntaran hacia el nuevo elemento
* el tamaño es actualizado
2. Inserción al inicio de la listaLa función devuelve -1 en caso de error, si no devuelve 0.

Etapas:
* asignación de memoria al nuevo elemento
* rellenar el campo de datos del nuevo elemento
* el puntero anterior del nuevo elemento apunta hacia NULL
* el puntero siguiente del nuevo elemento apunta hacia el 1er elemento
* el puntero anterior del 1er elemento apunta hacia el nuevo elemento
* el...