• Author / Uploaded
• Luana Gadêlha

Citation preview

1. Sesión 2 (laboratorio): Listas enlazadas

1.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. Lafigura 1 representa esta estructura de datos. Figura 1. 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: 

: Devuelve

public boolean isEmpty()

TRUE

o

, dependiendo de si la lista está

FALSE

o no vacía. 

public void insert(Object o)



public Object extract()



public void print(int n)



public void print()

: Añade un elemento al principio de la lista (el principio es el elemento apuntado por first en la figura 1). : 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. : 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. : 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. SOLUCION:

Node.java public class Node { private Object info; private Node next; public Node() { info = null; next = null; } public Node(Object o, Node n) { setInfo(o); setNext(n); } public void setInfo(Object o) { info = o; } public void setNext(Node n) { next = n; } public Object getInfo() { return info; }

}

public Node getNext() { return next; }

MySimpleLinkedList.java public class MySimpleLinkedList { // the reference to the first node is enough // to characterize a list protected Node first; // a list is created in an empty state public MySimpleLinkedList() { first = null; } // the new element is located before the // former first node public void insert(Object o) { // step by step code. Could be done in less lines // a node that stores the object and links nowhere Node tmp = new Node(o, null);

}

// the following sentence has no problem with null values of "first" tmp.setNext(first); // we move the "first" reference first = tmp;

// extracts the first element and returns its object public Object extract() { Object out = null; // if first is null, you cannot call its methods if (!isEmpty()) { out = first.getInfo(); first = first.getNext(); } // if the list is empty, null should be returned, but this is // the default value of "out" return out; } public void print(int n) { // if the list is empty, do nothing if (!isEmpty()) { Node tmp = first; // iterates until i reaches n or the list is finished. for (int i = 0; i < n; i++) { tmp = tmp.getNext(); if (tmp == null) return; // the list is finished } System.out.println(tmp.getInfo()); }

}

public void print() { // if the list is empty, do nothing if (!isEmpty()) { Node tmp = first; // iterates until the list is finished while (tmp != null) { System.out.println(tmp.getInfo()); tmp = tmp.getNext(); } } }

}

public boolean isEmpty() { if (first == null) return true; else return false; }

MySimpleLinkedListTest.java public class MySimpleLinkedListTest { public static void main(String args[]) { // just instantiate one object and call the methods. // I'm sure you can do it better than this code MySimpleLinkedList sll = new MySimpleLinkedList(); sll.insert(new sll.insert(new sll.insert(new sll.insert(new sll.insert(new

Integer(1)); Integer(2)); Integer(3)); Integer(4)); Integer(5));

sll.print(); sll.print(0); sll.print(1); sll.print(2); sll.print(3); sll.print(4); System.out.println(sll.extract()); System.out.println(sll.extract()); System.out.println(sll.extract()); System.out.println(sll.extract()); System.out.println(sll.extract()); }

sll.print();

}

1.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)



public Object extract(int n)



public String toString(int n)



public String toString()

: Inserta un nuevo elemento en la lista, colocandolo en la posición n. Si nes 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. : 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. : 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. : 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. SOLUCION: MyAdvancedLinkedList.java public class MyAdvancedLinkedList extends MySimpleLinkedList { // this code is the same than writting nothing. // That is, there is no need to write it public MyAdvancedLinkedList() { super(); } // insert one object in a specific position public void insert(Object o, int n) { if (isEmpty() || n