En esta práctica hay que diseñar y construir una aplicación que implemente distintos tipos de listas doblemente enlazadas cuyo funcionamiento se ejemplificará en el mantenimiento de una agenda personal. El propósito de esta práctica es además de la propia implementación de las estructuras de datos la utilización adecuada de las funcionalidades que Java proporciona mediante los mecanismos de herencia e interfaces.

Primero se creará una clase abstracta ListaDoblementeEnlazada que como su nombre indica estará formada por nodos que contienen un enlace al siguiente elemento y un enlace al elemento anterior de la lista. Con el propósito de que esta lista sea general los nodos podrán contener como información de contenido cualquier tipo de objeto.

Esta ListaDoblementeEnlazada además de la información necesaria para la gestión de la lista, incorpora y mantiene un 'cursor' que permite recorrer la lista, e implementa el siguiente protocolo:

boolean estaVacia() // devuelve true si la lista no contiene ningún nodo

void avanzar() // avanza el cursor al siguiente nodo -si lo hubiera, si no se queda en el actual-

void retroceder() // avanza el cursor al nodo anterior -si lo hubiera, si no se queda en actual-

void irAlPrincipio() // lleva el cursor al primer elemento de la lista.

void irAlFinal() // lleva el cursor al ultimo elemento de la lista. --- la implementación puede

mantener explicitamente referencias al principio y al final para que esto ocurra en O(1) ---

void borrarActual() // borra el nodo donde esta situado actualmente el cursor

Object obtenerItemActual() // devuelve el contenido del nodo al que referencia el cursor

void insertarAntes(Object info); // inserta el contenido 'info' en un nodo anterior a la posición actual referenciada por el cursor

void insertarDepues(Object info) // inserta el contenido 'info' después del nodo referenciado por el cursor

void estaAlFinal() // devuelve true si el cursor está en el último nodo de la lista

void reemplazarActual(Object info) // modifica la información contenida en el nodo actual

 

Además la clase incluirá otros métodos de utilidad general que utilizan las funcionalidades anteriores como son:

boolean eliminarItem(Object info); // elimina la primera ocurrencia del objeto en la lista (dev. False si no está)

void mostrarLista(); // presenta por pantalla la lista desde el primero al último elemento

void mostrarListaInvertida() // presenta por pantalla la lista desde el último al primer elemento

 

Así mismo se incluirán los métodos abstractos:

void insertar(Object obj) // inserta el elemento especificado en la lista

int buscar(Object obj) // devuelve el índice desde la cabecera del elemento buscado (-1 si no está)

 

La clase ListaDoblementeEnlazada se especializará mediante otras dos clases ListaDoblementeEnlazadaOrdenada y ListaDoblementeEnlazadaNoOrdenada. La segunda de estas clases mantendrá también una lista doblemente enlazada de objetos extendiendo las funcionalidades de la clase padre para incluir nuevas operaciones (p.e. la concatenación de listas, añadir un array de objetos a la lista). La clase ListaDoblementeEnlazadaOrdenada mantiene una lista doblemente enlazada y ordenada de objetos. Por tanto, los objetos a almacenar en dicha lista tienen que poder ser ordenados. Con dicho propósito se impone como limitación para la pertenencia a dicha lista de que los objetos a incluir en ella implementen el siguiente interfaz ObjetoOrdenado:

/** interfaz que declara el tipo de objetos ordenados */

public interface ObjetoOrdenado {

 

/** devuelve <0, >0 o igual a 0 segun el objeto sea menor, mayor o igual que el
* argumento */

public int compareTo(ObjetoOrdenado obj);

 

/** devuelve true si los dos objetos son iguales */

public boolean equals(ObjetoOrdenado obj);

}

 

La implementación de esta interfaz determinará cúal es el criterio de comparación para la ordenación de los objetos concretos a introducir en la lista ordenada.

Finalmente, el funcionamiento de los dos tipos de listas especializadas se ejemplificará mediante una aplicación interactiva que permita el mantenimiento de una agenda personal. Dicha agenda debe ser capaz de contener las fichas de un número arbitrario de personas para las cuales se almacenará el nombre, edad y correo electrónico. El criterio de ordenación de la agenda es el del orden alfabético de nombres. El listado de la agenda se podrá realizar de forma ordenada por nombres y según el orden en el cual fueron introducidos los datos para lo cual se mantendrán dos listas paralelas una ordenada y otra no ordenada.

Parte opcional

Además de las dos opciones indicadas para añadir a la funcionalidad de la lista ListaDoblementeEnlazadaNoOrdenada también se pueden introducir otras tal y como se hace en la clase clase LinkedList de Java 1.2.

Este diseño está limitado por el hecho de que sólo se puede tener un cursor sobre la lista. En la realidad esto se suele tratar de forma genérica mediante los iteradores que permiten tener tantos cursores o referencias a una lista como se deseen. Por tanto este diseño se puede ampliar añadiendo iteradores. Como referencia sobre su funcionamiento se puede consultar la clase LinkedList y el interface ListIterator en el API de Java 1.2.

Notas

Este enunciado es el punto de partida para la realización de la práctica pero puede verse complementado, modificado o simplificado con las explicaciones de la clase teórica.

Si hay alguna funcionalidad de una clase que no se utiliza en la aplicación final de la agenda se probará (si ésto es posible) en el programa principal de la clase correspondiente contribuyendo con ello a la documentación del código por la existencia de ejemplos de uso.

La lectura interactiva de datos se realizará mediante el paquete de lectura (esi.jar) proporcionado en clase. El código java para obtener dicho fichero también está disponible en http://bogart.sip.ucm.es/~balta/docencia.html.

Memoria de la práctica

Se entregará el código correctamente comentado y formateado, así como la documentación generada automáticamente mediante javadoc siguiendo las pautas explicadas en clase.

No hay que entregar el disquete con el código (aunque el profesor puede comprobar el correcto funcionamiento de la práctica en el ordenador). Cada grupo entregará la memoria exclusivamente en el laboratorio y en el turno correspondiente. La fecha límite de entrega de la memoria es la semana del 13 de Marzo.