Tabla de contenidos
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?
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(); }
public class Node<E> { private E info; private Node<E> next; public Node(E info, Node<E> next) { this.info = info; this.next = next; } public Node(E info) { this(info, null); } public Node() { this(null, null); } public E getInfo() { return this.info; } public Node<E> getNext() { return this.next; } public void setInfo(E info) { this.info = info; } public void setNext(Node<E> next) { this.next = next; } public String toString() { if (info != null) { return info.toString(); } else { return null; } } }
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?
Node<E>
que acabas de implementar).
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.
public class MyBasicLinkedList<E> { protected Node<E> first; public MyBasicLinkedList() { this.first = null; } public Node<E> getFirst() { return this.first; } public void setFirst(Node<E> first) { this.first = first; } public boolean isEmpty() { return (this.first == null); } public void insert(E info) { Node<E> newNode = new Node<E>(info); newNode.setNext(this.first); first = newNode; } public E extract() { E data = null; if (this.first != null) { data = this.first.getInfo(); this.first = this.first.getNext(); } return data; } public void insert(E info, Node<E> previous) { if(previous != null) { Node<E> newNode = new Node<E>(info); newNode.setNext(previous.getNext()); previous.setNext(newNode); } } public E extract(Node<E> previous) { E data = null; if(previous != null && previous.getNext()!=null) { data = previous.getNext().getInfo(); previous.setNext(previous.getNext().getNext()); } return data; } public int size() { int size = 0; Node<E> current = this.first; while(current != null) { size++; current = current.getNext(); } return size; } public String toString() { String listText = ""; Node<E> current = this.first; while(current != null) { listText = listText + current.getInfo().toString(); if(current.getNext() != null) { listText = listText + " -> "; } current = current.getNext(); } return listText; } public void print() { System.out.println(this); } public Node<E> searchNode(E info) { Node<E> targetNode = null; Node<E> currentNode = this.first; while(currentNode != null && !currentNode.getInfo().equals(info)) { currentNode = currentNode.getNext(); } if(currentNode!=null) { targetNode = currentNode; } return targetNode; } public Node<E> searchNode(int n) { Node<E> targetNode = null; Node<E> currentNode = this.first; int counter = 0; while(currentNode != null && counter<n) { currentNode = currentNode.getNext(); counter++; } if(currentNode!=null) { targetNode = currentNode; } return targetNode; } public Node<E> searchLastNode() { Node<E> current = this.first; while(current != null && current.getNext() != null) { current = current.getNext(); } return current; } public int search(E info) { Node<E> current = this.first; int infoPosition = -1; if(!isEmpty()) { infoPosition = 0; while(current != null && !current.getInfo().equals(info)) { infoPosition++; current = current.getNext(); } } return infoPosition; } public int numberOfOccurrences(E info) { int counter = 0; Node<E> current = this.first; while(current != null) { if(current.getInfo().equals(info)){ counter++; } current = current.getNext(); } return counter; } }
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?
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.
public class MyAdvancedLinkedList<E> extends MyBasicLinkedList<E> { public MyAdvancedLinkedList() { super(); } public void insert(E info, int position) { Node<E> previousNode = searchNode(position-1); if(previousNode != null) { insert(info, previousNode); } } public E extract(int position) { Node<E> previousNode = searchNode(position-1); E info = null; if(previousNode != null) { info = extract(previousNode); } return info; } public void insertLast(E info) { Node<E> lastNode = searchLastNode(); if(lastNode != null) { insert(info,lastNode); } else { this.first = new Node<E>(info);; } } public E extractLast() { E info = null; Node<E> current = this.first; int listSize = size(); if(!isEmpty()) { if(listSize == 1) { info = current.getInfo(); this.first = null; } else { Node<E> previousLastNode = searchNode(listSize-2); info = extract(previousLastNode); } } return info; } public void print(int position) { Node<E> current = this.first; int counter = 0; String listText = ""; if(!isEmpty()) { while(current != null && counter < position ) { current = current.getNext(); counter++; } while(current != null) { listText = listText + current.getInfo().toString(); if(current.getNext() != null) { listText = listText + " -> "; } current = current.getNext(); } } System.out.println(listText); } }