Table of Contents
The first step in order to implement a linked list is to create
the class that will represent the nodes the list is made of. In
this exercise you are asked to program the Node<E>
class. This class will represent the nodes of the linked
list. Take a look at the slides from theory class, they will be
of great help in order to solve this task.
Before coding the Node<E>
class,
follow these guidelines:
Node<E>
class extend any
class? Does it implement any interface?
public String toString()
method.
This method will return the text representation of
the object stored by the node (info
).
Create a class called NodeTest
in order
to test the Node<E>
class you
just coded. Among the tests you should perform,
try to create several nodes of different types
(String
, Integer
...) and
print on screen the textual representation of each
node (remember you implemented the toString()
method in order to obtain that representation).
Execute the following code as part of the tests
in NodeTest
class. What happens with
this code? At which point is the error detected:
compilation or execution time? Why?
public static void main(String args[]) { //Your testing code goes here Node<Integer> myNode1 = new Node<Integer>(); String data = myNode1.getInfo(); }
At this point you already have implemented and tested the
class that will represent the nodes of the list. Therefore,
you can proceed to implement the class that will represent
the list itself: MyBasicLinkedList<E>
.
As before, follow these guidelines:
MyBasicLinkedList<E>
extend any
class? Does it implement any interface? Does it use objects
from any other class?
Node<E>
might be useful.
Create a MyBasicLinkedListTest
class in order
to test the MyBasicLinkedList<E>
class
as you implement it.
Implement the following methods. Keep the slides from theory class close to you, they will help you a lot to accomplish this task.
isEmpty()
. This method returns
true
if the list is empty, or
false
otherwise.
insert(E info)
.
This method inserts a new node at the beginning of
the list. The new node will store the information
in the argument. In any case, the method must
return nothing.
extract()
. The method extract the first node
of the list, and returns the information stored in the
extracted node. Pay special attention to the case in which
the list is empty. In this situation the method will return
null
. Be careful also with the case in which
the list has an only element.
insert(E info,
Node<E> previous)
. The functionality of this
method is to insert a new node, which content will be
info
, after the node previous
.
Consider carefully the cases in which the list is empty and
when previous
is null
.
extract(Node<E> previous)
. This method
extracts from the list the following node to
previous
, and returns the object stored by
this extracted node. Once again, pay attention to the case
in which previous
or its next node are
null
.
size()
. This method return an integer indicating
the number of nodes in the list. If the list is empty, the
method will return 0.
toString()
. This method returns an String
with the textual
representation of the list. This string will be the
concatenation of the textual representation of each element,
followed by ->, except in the case of the last node. For
example, for a list with four nodes storing objects of
type String
, where in each node of the list
is stored the first four letters of the alphabet, the result
of this method would be "a -> b -> c -> d". Remember to use
the most appropriate method from Node<E>
class in order to obtain its textual representation.
print()
. This method prints into the standard
output the textual representation of the list. Think first
the easiest way to implement this method, taking advantage of
the methods you already wrote.
searchNode(E info)
. This method returns the
object Node<E>
containing info
.
If several nodes store info
, the one to be
returned will be the first one. If any node stores
info
, the method will return null
.
Do not forget to pay attention to the case in which the
list is empty.
searchNode(int n)
. This method returns the
Node<E>
object in the position
n
of the list. Consider that the first element
of the list corresponds to the position 0. If the list has
less than n
elements, the method will return
null
. Consider carefully the case in which the
list is empty.
searchLastNode()
. This method returns the
Node<E>
object corresponding to the
last node of the list. Once again, consider the case in
which the list is empty.
search(E info)
returns an int
indicating the position of the object info
in the list. If the info
object is not
in the list, the method must return -1.
As in all the previous cases, be careful
when the list is empty.
Check that your methods work correctly in the test class you created before. Test every method, at least, for these cases: an empty list, a list with an only element, and a list with 2 or more elements. In the search methods, besides, add the cases in which the searched element exists, does not exist and is repeated in the list. Check all the possible cases, and pay special attention to the exceptional cases. Testing is not demonstrating that your code works for a particular case, but that there are no errors even in any of the most extreme cases.
So far, we have implemented the most basic operations that can
be done with linked lists. In this exercise we will add more
complex functionalities, in which you will need to apply the
observations you gathered in the previous exercises (check
that the nodes are not null
, comparisons between
the objects stored by the nodes, traversing a list...).
In order to extend the functionality of MyBasicLinkedList<E>
class, create a new class called MyAdvancedLinkedList<E>
that will inherit all the previous functionality. In order to write the
new class, follow these guidelines:
MyAdvancedLinkedList<E>
extend any class?
Does it implement any interface? Does it use objects from another class?
Create a MyAdvancedLinkedListTest
class to test
the MyAdvancedLinkedList<E>
class as you
write it.
Code now the following methods:
insert(E info, int position)
. The method
inserts a new node storing info
in the
position position
of the list (the first
node corresponds to the position 0). If the list has
less than position
elements, then the
method will do nothing. Observe carefully the methods
you already wrote and decide if you can use any of them
to complete this new method.
extract(int position)
. This method extracts
the node in the position position
(the first
node of the list corresponds to the position 0),
preserving the rest of the list and returning the
information stored in the extracted node. If the list
has less than position
elements, the method
returns null
and do nothing. Once again,
take advantage of the methods you already have available.
insertLast(E info)
. This method inserts
a new node, containing info
at the end
of the list. Pay special attention to the case in which
the list is empty, and try to use methods you already
implemented.
removeLast()
. This method extracts
the last node of the list, and returns the object
stored by that node. If the list is empty, the
method will return null
. Be careful
with the case in which the list has an only
element, and bear in mind the methods you
already wrote.
print(int position)
. This method prints in
the standard output the textual representation of every
node starting at position position
of the
list (the first node corresponds to the position 0). If
the list has less than position
nodes,
nothing will be printed. The textual representation will
be the concatenation of the textual representation of
every node, followed by ->, except for the last node. For
example, imagine a list of four elements, storing Strings.
Every node of the list stores one of the first letters
of the alphabet. If print(2)
is called over this
list, the result will be "c -> d". Remember to user the
most appropriate method of Node<E>
class in order to get its textual representation.
Test the methods with the MyAdvancedLinkedListTest
class.
Check each one of them, at least, for these cases: an empty list,
a list containing an only element, a list with 2 or more elements.
In the cases of insert/extraction in a position, besides, add the
cases where the position is -1, 0, 1 and a number greater than the
list size. Test all the possible cases you come up with, and pay
special attention to the most exceptional ones. Once again, testing is not demonstrating that your code
works for a particular case, but that there are no errors
even in any of the most extreme cases