Practica 6Lista doblemente ligada

Estructuras de datos

1. Meta

Que el alumno domine el manejo de informacion almacenada en una Lista, en su implementacion como listadoblemente ligada.

2. Objetivos

Al finalizar la practica el alumno sera capaz de:

• Visualizar como se almacena una lista en la memoria de la computadora mediante el uso de nodos conreferencias a su elemento anterior y su elemento siguiente.

• Programar dicha representacion en un lenguaje orientado a objetos.

3. AntecedentesDefinicion 1

Una lista es:

Lista =

Lista vacıa

Dato seguido de otra lista

Alternativamente:

Definicion 2

Una lista es una secuencia de cero a mas elementos de un tipo determinado (que por lo general se denominaratipo-elemento). Se representa como una sucesion de elementos separados por comas:

a0, a1, ..., an−1 (1)

donde n ≥ 0 y cada ai es del tipo tipo-elemento.

1

• Al numero n de elementos se le llama longitud de la lista.

• a0 es el primer elemento y an−1 es el ultimo elemento.

• Si n = 0, se tiene una lista vacıa, es decir, que no tiene elementos. Aho (1983)

En este caso utilizaremos como definicion del tipo de datos abstracto, la interfaz definida por Oracle:

http://docs.oracle.com/javase/8/docs/api/java/util/List.html.

Actividad 1

Lee la definicion de la interfaz List<E>. ¿Te queda claro lo que debe hacer cada metodo? Si no, pregunta atu ayudante.

Actividad 2

Elige los metodos que consideres mas importantes y dibuja como te imaginas que se ve la lista antes demandar llamar un metodo y que le sucede cuando este es invocado.

Una lista doblemente ligada es una implementacion de la estructura de datos lista, que se caracteriza por:

1. Guardar los datos de la lista dentro de nodos que hacen referencia al nodo con el dato anterior y al nodocon el siguiente dato.

2. Tener una referencia al primer y ultimo nodo.3. Tener un tamano dinamico, pues el numero de datos que se puede almacenar esta limitado unicamente por

la memoria de la computadora y el tamano de la lista se incrementa y decrementa conforme se insertan oeliminan datos de ella.

4. Es facil recorrerla de inicio a fin o de fin a inicio.

4. Desarrollo

Para implementar el TDA Lista se debera extender la clase abstracta ColeccionAbstracta<E>, implementarla interfaz List<E>. Esto se debera hacer en una clase ListaDoblementeLigada<E>.

A continuacion presentamos la clase abstracta ColeccionAbstracta<E>. Observa que no todos los metodoshan sido implementados.

1 /*2 * Co digo utilizado para el curso de Estructuras de Datos.3 * Versi on para estudiantes .4 */5 package estructuras . lineales ;6

7 import java.util. Arrays ;8 import java.util. Collection ;9 import java.util. Iterator ;

10

11 /**12 * Implementaci on gen e rica de varios me todos aprovechando el iterador ,13 * que deber a ser implementado por las subclases.14 * @author veronica15 */

2

16 public abstract class ColeccionAbstracta <E> implements Collection <E> {17

18 /**19 * Indica si esta colecci on contiene al objeto <code >o</code >.20 * Asume que puede haber elementos nulos dentro de la estructura .21 * @param o El objeto a buscar.22 * @return <code >true </code > si el objeto se encuentra .23 */24 @Override25 public boolean contains ( Object o) {26 for(E elemento : this) {27 if(o == null ? elemento == null : o. equals ( elemento )) return true;28 }29 return false ;30 }31

32 /**33 * Devuelve un arreglo con referencias a todos los elementos de la colecci on34 * en el orden definido por su iterador.35 * @return arreglo con referencias .36 */37 @Override38 public Object [] toArray () {39 // TODO: implementa este me todo.40 }41

42 /**43 * Devuelve un arreglo con referencias a todos los elementos de la colecci on,44 * del mismo tipo que el arreglo enviado como par ametro ,45 * en el orden definido por su iterador.46 * Para detalles sobre cuando se usa el arreglo enviado o cu a ndo se crea47 * uno nuevo , ver documentaci on en la interfaz <code >Collection </code >.48 * @return arreglo con referencias .49 */50 @Override51 public <T> T[] toArray (T[] a) {52 int tam = size ();53 if(a. length < tam ){54 a = Arrays . copyOf (a, tam );55 }56 int i = 0;57 for(E obj : this ){58 a[i++] = (T)obj;59 }60 if(a. length > tam ){61 a[tam] = null;62 }63 return a;64 }65

66 /**67 * Indica si esta colecci on contiene a todos los elementos de <code >c</code >.68 * @param Estructura con los elementos a revisar.69 * @return <code >true </code > si esta estructura contiene a todos los elementos70 * de <code >c</code >.71 */72 @Override73 public boolean containsAll ( Collection <?> c) {74 for( Object o : c) {75 if (! this. contains (c)) return false ;76 }77 return true;78 }79

80 /**

3

81 * Intenta agregar a todos los elementos en <code >c</code >.82 * Si la estructura subyacente impide que alg un elemento se agregue ,83 * lanzando la excepci on correspondiente , este me todo permitir a que la84 * excepci on se propague.85 * @param c86 * @return87 */88 @Override89 public boolean addAll ( Collection <? extends E> c) {90 boolean cambio = false ;91 for(E elem : c) {92 if(add(elem) == true) cambio = true;93 }94 return cambio ;95 }96

97 /**98 * Remueve un solo ejemplar del elemento especificado de esta colecci on, si99 * se encuentra presente y satisface (o== null ? e== null : o.equals(e)).

100 * @param o elemento a remover si se encuentra presente.101 * @return true si la estructura cambi o al remover el elemento.102 */103 @Override104 public boolean remove ( Object o) {105 Iterator <E> it = this. iterator ();106 while (it. hasNext ()) {107 E elemento = it.next ();108 if (o == null ? elemento == null : o. equals ( elemento )) {109 it. remove ();110 return true;111 }112 }113 return false ;114 }115

116 /**117 * Se asegura de que esta colecci on no contenga ninguna instancia que est e118 * en <code >c</code >.119 * Si la estructura subyacente impide que alg un elemento se elimine ,120 * lanzando la excepci on correspondiente , este me todo permitir a que la121 * excepci on se propague.122 * @param c123 * @return124 */125 @Override126 public boolean removeAll ( Collection <?> c) {127 // TODO: implementa este me todo.128 }129

130 /**131 * Remueve todos los elementos que no se encuentren en <code >c</code >.132 * @param c Colecci on con los elementos que se desea conservar .133 * @return <code >true <code > si esta colecci on fue modificada .134 */135 @Override136 public boolean retainAll ( Collection <?> c) {137 // TODO: implementa este me todo.138 }139

140 /**141 * Remueve a todos los elementos de la colecci on uno por uno , en el orden142 * dictado por el iterador.143 */144 @Override145 public void clear () {

4

146 Iterator <E> it = iterator ();147 while (it. hasNext ()) {148 it. remove ();149 }150 }151

152 }

1. Completa el codigo faltante en la clase ColeccionAbstracta<E>.

2. Crea la clase ListaDoblementeLigada<E>, que extiende ColeccionAbstracta<E> e implementa la in-terfaz List<E>.

5. Preguntas

1. Explica por que es necesario crear nodos.

2. Explica como funcionan los metodos para agregar y eliminar.

3. Si mantenemos los elementos ordenados alfabeticamente, por ejemplo, ¿cuando serıa mas eficiente agregarun elemento mediante el inicio o el final de la lista?

4. En que casos serıa mas eficiente obtener un elemento desde el inicio de la lista o desde el final de la lista.

6. Forma de entrega

• Asegurate de borrar todos los archivos generados, incluyendo archivos de respaldo usando ant clean.

• Copia el directorio Practica6 dentro de un directorio <apellido1 apellido2> donde apellido1 es elprimer apellido de un miembro del equipo y apellido2 es el primer apellido del otro miembro. Por ejemplo:marquez vazquez.

• Borra el directorio libs en la copia.

• Agrega un archivo reporte.pdf dentro del directorio Practica6 de la copia, con el nombre completo delos integrantes del equipo, las repuestas a las preguntas de la seccion anterior y cualquier comentario quequieras hacer sobre la practica.

• Comprime el directorio <apellido1 apellido2> en un archivo <apellido1 apellido2>.tar.gz. Porejemplo: marquez vazquez.tar.gz.

• Sube este archivo en la seccion correspondiente del aula virtual.

7. Forma de evaluacion

Para tu calificacion final se tomaran en cuenta los aspectos siguientes:

5

60 % Calificacion generada por las pruebas automaticas. Usaremos nuestros archivos, por lo quesi realizas modificaciones a tus copias, estas no tendran efecto al momento de calificar.

25 % Documentacion completa y adecuada. Entrega en el formato requerido, sin archivos .class,respaldos, bibliotecas de JUnit u otros no requeridos.

15 % Revision manual del codigo, para verificar que se cumpla con las especificaciones, que no sehaya copiado, etcetera.

ReferenciasAlfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, Data Structures and Algorithms Addison-Wesley,

1983. pp. 427.

Trad. Estructuras de datos y Algoritmos. Trad. America Vargas Villazon, Jorge Lozano Moreno (colaboracion deGuillermo Levine Gutierrez), 1998. 438 pp.

6