Universidad Carlos III de Madrid

Grado en Ingeniería Telemática/Grado en Ingeniería de Sistemas de Comunicaciones

Enero-Mayo 2014

Listas Enlazadas, Pilas y Colas

Tabla de contenidos

1. Sesión 2 (laboratorio): Listas enlazadas
1.1. Nodos con tipos genéricos
1.2. Listas enlazadas simples
1.3. Listas enlazadas: extendiendo la funcionalidad básica

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

Exercise Section1.1. Nodos con tipos genéricos

El primer paso para implementar una lista enlazada es crear la clase que representará los nodos que conforman dicha lista. En este ejercicio debes programar la clase Node<E>, que representará cada uno de los nodos de la lista enlazada. Las transparencias de la clase de teoría te pueden servir de ayuda en esta tarea.

Para implementar la clase Node<E>, sigue las siguientes pautas:

  • ¿Node<E> hereda de alguna clase? ¿Implementa alguna interfaz?
  • ¿Qué atributos tienes esta clase (tipo, acceso)?
  • Define, al menos, dos constructores que inicialicen estos atributos. Un constructor recibirá como parámetros el valor para todos los atributos, mientras que otro no recibirá ningún parámetro. Si lo crees conveniente, puedes definir más constructores. Recuerda que lo más correcto es inicializar explícitamente los atributos en el constructor más específico, y llamar a este constructor con los argumentos apropiados en el resto de constructores.
  • Implementa los métodos de acceso y modificación de los atributos que hayas definido.
  • Sobreescribe el método public String toString(). Este método devolverá la representación textual del objeto almacenado en el nodo (info).

Crea una clase NodeTest para probar la clase Node<E> que acabas de programar. Entre los tests, prueba a crear varios nodos con diferentes tipos (String, Integer...) e imprime por pantalla la representación textual del nodo (recuerda que has implementado el método toString() para obtener dicha representación).

Prueba a ejecutar el siguiente código como parte de las pruebas en NodeTest. ¿Qué ocurre con este código? ¿En qué momento se está detectando el error: compilación o ejecución? ¿Por qué? 

   public static void main(String args[]) {
        
        //Your testing code goes here
        
        Node<Integer> myNode1 = new Node<Integer>();
        String data = myNode1.getInfo();
   }

Exercise Section1.2. Listas enlazadas simples

En este punto ya tenemos implementada y probada la clase que representará los nodos de la lista. Por tanto, podemos proceder a implementar la clase que representará la lista en sí, MyBasicLinkedList<E>. Para ello, sigue la siguientes pautas:

  • ¿MyBasicLinkedList<E> hereda de alguna clase? ¿Implementa alguna interfaz? ¿Utiliza objetos de otra clase?
  • ¿Qué atributos tienes esta clase (tipo, acceso)? (Recuerda que te puede ser útil la clase Node<E> que acabas de implementar).
  • Define, al menos, un constructor que inicialice estos atributos. Si lo crees conveniente, puedes definir más constructores.
  • Implementa los métodos de acceso y modificación de los atributos que hayas definido.

Crea una clase MyBasicLinkedListTest para probar la clase MyBasicLinkedList<E> según la vayas implementando.

Implementa los siguientes métodos. Las transparencias de teoría te pueden ayudar para completar la tarea.

  • isEmpty(). Este método devuelve true si la lista está vacía, o false en caso contrario.
  • insert(E info). Este método añade un nuevo nodo al principio de la lista. Este nodo contendrá la información que se pasa al método por parámetro. En cualquier caso, el método no devuelve nada.
  • extract(). En este caso, el método elimina el primer nodo de la lista, y devuelve la información que estaba contenida en dicho nodo. Presta especial atención al caso en el que la lista está vacía, en cuyo caso se devolverá null. Ten cuidado tambien con el caso en que la lista tiene un unico elemento.
  • insert(E info, Node<E> previous). Su función será añadir un nuevo nodo, cuyo contenido será info, después del nodo previous. Considera detenidamente los casos en los que la lista está vacía y previous es null.
  • extract(Node<E> previous). Este método elimina de la lista el nodo siguiente a previous, y devuelve el contenido de dicho nodo. De nuevo, presta atención al caso en el que previous o el siguiente nodo son null.
  • size(). Este método devuelve un entero indicando el número de nodos en la lista. Si la lista está vacía, devolverá 0.
  • toString(). Este método devuelve la representación textual de la lista, que estará compuesta por la concatenación de la representación textual de cada elemento, seguido de ->, excepto en el caso del último nodo. Por ejemplo, para una lista de cuatro elementos que almacena objetos de tipo String, y en cada nodo de la lista están almacenadas las primeras cuatro letras del abecedario, el resultado de este método sería "a -> b -> c -> d". Recuerda usar el método más apropiado de Node<E> para obtener su representación textual.
  • print(). Este método imprime por salida estándar la representación textual de la lista. Piensa primero la forma más sencilla de implementar este método a partir de métodos previos.
  • searchNode(E info). Este método devuelve el objeto Node<E> que contiene info. Si varios nodos contienen info, se devolverá el primero de ellos. Si ninguno de ellos contiene esta información, se devolverá null. No olvides prestar atención al caso en que la lista esté vacía.
  • searchNode(int n). Este método devuelve el objeto Node<E> en la posición n de la lista. Se considera que el primer elemento de la lista corresponde con la posición 0. Si la lista tiene menos de n posiciones, se devolverá null. Considera cuidadosamente el caso en que la lista esté vacía.
  • searchLastNode(). Devuelve el objeto Node<E> correspondiente al último nodo de la lista. Nuevamente, presta atención al caso de que la lista sea vacía.
  • search(E info) devuelve un int indicando la posición en la lista del objeto info que se pasa por parámetro. Si el objeto info no está en la lista, se devuelve -1. Como en todos los casos anteriores, considera el caso en que la lista está vacía.

Prueba tus métodos en la clase de prueba que creaste al principio. Prueba cada uno de ellos, al menos, para estos casos: una lista vacía, una lista con un elemento, una lista con 2 o más elementos. En los casos de búsqueda, además, añade los casos en los que el elemento buscado existe, no existe, está repetido. Prueba toda la casuística que existe para cada caso, y presta especial atención a los casos excepcionales. Probar no es demostrar que funciona en un caso, sino que no hay error ni en los casos más extremos.

Exercise Section1.3. Listas enlazadas: extendiendo la funcionalidad básica

Hasta ahora hemos implementado las operaciones más básicas que se pueden realizar con listas enlazadas. En este ejercicio añadiremos funcionalidades más complejas en las que tendrás que aplicar las observaciones que has ido recopilando en los ejercicios anteriores (comprobar que los nodos no sean null, comparaciones entre los objetos almacenados por los nodos, recorrer una lista...).

Para extender la funcionalidad de la clase MyBasicLinkedList<E>, crea una nueva clase MyAdvancedLinkedList<E> que herede toda la funcionalidad que has definido anteriormente. Para implementar la nueva clase, plantéate antes las siguientes preguntas:

  • ¿MyAdvancedLinkedList<E> hereda de alguna clase? ¿Implementa alguna interfaz? ¿Utiliza objetos de otra clase?
  • En caso de heredar de alguna clase, vas a necesitar acceder a los atributos de la clase padre. Para que el código resulte más claro, comprueba que los modificadores de acceso de los atributos de la clase padre son los apropiados para que la clase que hereda (y sólo ella) pueda acceder a ellos directamente, sin necesidad de usar ningún método.
  • Define al menos un constructor para la nueva clase. Si hereda de alguna otra clase, recuerda llamar al constructor de la clase padre dentro del constructor de la clase hija.

Crea una clase MyAdvancedLinkedListTest para probar la clase MyAdvancedLinkedList<E> según la vayas implementando.

Implementa ahora los siguientes métodos:

  • insert(E info, int position). El método debe añadir un nuevo nodo que contenga la información info en la posición position de la lista (se considera que la primera posición de la lista es 0). Si la lista tiene menos de position elementos, el método no añadirá nada. Observa cuidadosamente los métodos que has progarmado hasta ahora y analiza si puedes usar alguno de ellos para implementar este método.
  • extract(int position). El método debe eliminar el nodo en la posición position (se considera que la primera posición de la lista es 0), preservando el resto de la lista y devolviendo la información contenida en el nodo eliminado. Si la lista tiene menos de position elementos, se debe devolver null y dejar la lista intacta. De nuevo, trata de aprovechar los métodos que has programado hasta ahora.
  • insertLast(E info). Este método inserta un nuevo nodo, que contendrá la información info al final de la lista. Presta atención al caso en que la lista esté vacía, y trata de utilizar funciones que ya están hechas.
  • removeLast(). Este método elimina el último nodo de la lista, y devuelve la información que contenía dicho nodo. Si la lista está vacía, se deberá devolver null. Ten cuidado también con el caso en que la lista tiene un único elemento, y ten en mente los métodos que has escrito hasta ahora.
  • print(int position). Este método debe imprimir la representación textual de todos los nodos a partir de la posición position (se considera que el primer nodo de la lista corresponde a la posición 0). Si la lista tiene menos de position elementos, no se debe imprimir nada. La representación estará compuesta por la concatenación de la representación textual de cada elemento, seguido de ->, excepto en el caso del último nodo. Por ejemplo, supón una lista de cuatro elementos que almacena objetos de tipo String. Cada nodo de la lista almacena una de las primeras cuatro letras del abecedario. Sobre esta lista se llama al método print(2). El resultado de este método sería "c -> d". Recuerda usar el método más apropiado de Node<E> para obtener su representación textual.

Prueba tus métodos en la clase MyAdvancedLinkedListTest. Prueba cada uno de ellos, al menos, para estos casos: una lista vacía, una lista con un elemento, una lista con 2 o más elementos. En los casos de insercción/extracción en una posición, además, añade los casos en los que la posición es -1, 0, 1 y un número mayor que el tamaño de la lista. Prueba toda la casuística que existe para cada caso, y presta especial atención a los casos excepcionales. De nuevo, probar no es demostrar que funciona en un caso, sino que no hay error ni en los casos más extremos.