Universidad Carlos III de Madrid

Ingeniería de Telecomunicación

Enero-Mayo 2010 / January-May 2010

Listas Enlazadas, Pilas y Colas

Tabla de contenidos

1. Sesión 2 (laboratorio): Listas enlazadas
1.1. Listas enlazadas simples
1.2. Más sobre listas enlazadas simples
2. Actividades para casa
2.1. Listas enlazadas simples
2.2. Listas enlazadas circulares

Lab Section1. Sesión 2 (laboratorio): Listas enlazadas

Exercise Section1.1. Listas enlazadas simples

Objetivo

Practicar con algunos ejercicios básicos de listas enlazadas simples.

Repaso teórico

Una lista enlazada simple es una estructura de datos en la que cada elemento apunta al siguiente. De este modo, teniendo la referencia del principio de la lista podemos acceder a todos los elementos de la misma. La figura 1 representa esta estructura de datos.

Figura 1. Representación gráfica de una lista enlazada simple

Representación gráfica de una lista enlazada simple

La lista enlazada se compone de nodos (objetos instanciados pertenecientes a la clase Node), cada uno de los cuales tiene dos únicas tareas: guardar la información de la posición i y ofrecer una referencia a la posición i+1.

Ejercicio

Implementa una clase que modele una lista enlazada simple. Debes seguir los siguientes pasos:

  1. Lee detenidamente los requisitos funcionales de la clase.

  2. Piensa en el diseño de la estructura de datos. ¿Heredará de alguna otra clase? ¿Implementará alguna interfaz? ¿Utilizará objetos de alguna otra clase? Te será útil tener papel y boli a mano.

  3. En paralelo a la implementación de la clase que se pide, programa una clase de prueba que simplemente cree un objeto de tipo lista enlazada simple y ponga a prueba sus diferentes métodos.

La clase que programes se deberá llamar MySimpleLinkedList. Utiliza para ello una estructura interna de tipo Node (tendrás que programar dicha clase). Los métodos públicos que debe ofrecer la clase MySimpleLinkedList son:

  • public boolean isEmpty(): Devuelve TRUE o FALSE, dependiendo de si la lista está o no vacía.

  • public void insert(Object o): Añade un elemento al principio de la lista (el principio es el elemento apuntado por first en la figura 1).

  • public Object extract(): Elimina de la lista el elemento que está al principio de la misma y devuelve el valor que dicho elemento tenía almacenado. Ojo al caso en que la lista no contenga ningún elemento.

  • public void print(int n): Imprime por salida estándar el valor del objeto almacenado en la posición n (se empieza a contar en 0). Si la lista tiene menos de n-1 posiciones, no imprime nada. La ejecución de este método no debe modificar el contenido de la lista.

  • public void print(): Imprime la lista desde la posición inicial hasta la posición final. La ejecución de este método no debe modificar el contenido de la lista.

No olvides implementar una clase MySimpleLinkedListTest que sirva para comprobar el buen funcionamiento del código que vas desarrollando.

Exercise Section1.2. Más sobre listas enlazadas simples

Objetivo

Practicar con algunos ejercicios básicos de listas enlazadas simples.

Repaso teórico

Si ya dispones de la implementación de una lista enlazada, puedes reutilizar el código simplemente creando una nueva clase que herede de la que ya teníamos. Así, tendrás gran parte de la funcionalidad con muy poco esfuerzo.

Ejercicio

Implementa una clase que modele una lista enlazada. Puedes basarte en MySimpleLinkedList. Debes seguir los siguientes pasos:

  1. Lee detenidamente los requisitos funcionales de la clase. Asegurate de que has entendido la descripción de cada uno de los métodos a implementar.

  2. Piensa en el diseño de la estructura de datos. ¿Heredará de alguna otra clase? ¿Implementará alguna interfaz? ¿Utilizará objetos de alguna otra clase? Te será útil tener papel y boli a mano.

  3. En paralelo a la implementación de la clase que se pide, programa una clase de prueba que simplemente cree un objeto de tipo lista enlazada simple y ponga a prueba sus diferentes métodos.

La clase que programes se deberá llamar MyAdvancedLinkedList. Los métodos públicos que debe ofrecer dicha clase son:

  • public void insert(Object o, int n): Inserta un nuevo elemento en la lista, colocandolo en la posición n. Si n es mayor que el tamaño de la lista, lo inserta en la última posición. Si la lista está vacía, lo inserta como primer y único elemento.

  • public Object extract(int n): Elimina de la lista el elemento que está en la posición n y devuelve el valor que dicho elemento tenía almacenado. Tras la ejecución del método, la posición n-1 deberá apuntar a la posición n+1. Si la lista es demasiado corta, elimina el último elemento.

  • public String toString(int n): Devuelve un String, que es la representación textual del objeto almacenado en la posición n de la lista. Si la lista tiene menos de n-1 posiciones, el método devuelve null. La ejecución de este método no debe modificar el contenido de la lista.

  • public String toString(): Devuelve un String, que es el resultado de concatenar la representación textual cada uno de los objetos de la lista. Inserta un espacio entre cada dos elementos. La ejecución de este método no debe modificar el contenido de la lista.

No olvides implementar una clase MyAdvancedLinkedListTest que sirva para comprobar el buen funcionamiento del código que vas desarrollando.

Homework Section2. Actividades para casa

Exercise Section2.1. Listas enlazadas simples

Objetivo

Practicar con algunos ejercicios básicos de listas enlazadas simples.

Ejercicio

  • Si no tuviste tiempo suficiente, termina los ejercicios de clase. Si ya los terminaste, dedica unos minutos a repasarlos.

    Implementa además los siguientes métodos en la clase MyAdvancedLinkedList:

  • En la clase MySimpleLinkedList se pedía un método para extraer un elemento del principio de la lista y otro para añadir un objeto al principio de la lista.

    ¿Se puede añadir un objeto al final de la lista? Si crees que se puede, implementa dicho método en MyAdvancedLinkedList.

    ¿Se puede extraer un objeto del final de la lista? Si crees que se puede, implementa dicho método en MyAdvancedLinkedList.

  • Considera e implementa una nueva versión de los métodos print() y print(int n) en la que se reutilizen los métodos toString() y toString(int n). Recuerda que la relación de herencia permite sobreescribir métodos heredados.

Exercise Section2.2. Listas enlazadas circulares

Objetivo

Observar posibles estructuras que derivan de las listas enlazadas y entender las similitudes y diferencias con las listas simples.

Repaso teórico

Una lista enlazada simple es una estructura de datos en la que cada elemento apunta al siguiente. De este modo, teniendo la referencia del principio de la lista podemos acceder a todos los elementos de la misma. La figura 2 representa esta estructura de datos.

Figura 2. Representación gráfica de una lista enlazada simple

Representación gráfica de una lista enlazada simple

La lista enlazada circular no es más que una lista enlazada en la que el último elemento de la lista está enlazado al primer elemento de la lista, formando un círculo cerrado. La estructura está representada en la figura 3.

Figura 3. Representación gráfica de una lista enlazada circular

Representación gráfica de una lista enlazada circular

Ejercicio

La clase CircularLinkedList modela una lista enlazada circular. Parte de esta clase ya está implementada. Para empezar, descargala y observa su código.

CircularLinkedList.java

El método public static CircularLinkedList getExample() devuelve una lista circular con un número de elementos aleatorio entre 0 y 9. Dichos elementos son objetos tipo Integer con un valor aleatorio entre -25 y 25. Puedes utilizar dicho método para obtener una lista circular con la que hacer pruebas a lo largo de este ejercicio.

Implementa, en la clase CircularLinkedList que has descargado, los siguientes métodos:

  • public int size(): Devuelve el número de elementos que hay en la lista.

    Después de implementar este método, ¿qué coste y qué beneficio tendría almacenar el tamaño en una variable, en vez de calcularlo cada vez que se necesita? ¿En qué situaciones es preferible cada una de las alternativas?

  • public String toString(): Devuelve un String, que es el resultado de concatenar la representación textual cada uno de los objetos de la lista (una vuelta completa a la lista). El primer elemento será el elemento al que apunta position. La ejecución de este método no debe modificar el contenido de la lista. Tampoco debes modificar position.

  • public Object[] toArray(): Devuelve un array de objectos tipo Object, en cuyas posiciones habrá referencias a los objetos almacenados en la lista circular. Obviamente, el array no será circular. El primer elemento del array (posición 0) será el que está apuntado por position.

  • public MySimpleLinkedList toSimpleLinkedList(): Devuelve una lista enlazada simple, en cuyas posiciones habrá referencias a los objetos almacenados en la lista circular. El primer elemento de la lista devuelta será el que está apuntado por position.

No olvides implementar una clase CircularLinkedListTest que sirva para comprobar el buen funcionamiento del código que vas desarrollando. Es en esta clase de test donde usarás el método public static CircularLinkedList getExample().