$ mkdir ~/cs170/labs/lab27 $ cd ~/cs170/labs/lab27
As normal, in computer science we worry about efficiency a lot.
One way that we can iterate over every element of a linked list is
to request individual elements out of the list. You can accomplish
this by writing a method to your Linked List called getNth
Write a new method of your linked list class
called getNth. This method takes one paramters, an
integer in the range \([0, numElements)\), and returns an integer
(the data contained in the Nth node contained in the linked list.
Make sure you test your methods carefully. Think about what the edge cases are, and how to handle them appropriately.
The above method makes it possible to iterate over the entirety of the list. However, it is slightly less efficient. It takes \(O(n^2)\) time to iterate over the linear list. Which is not good at all. A different solution is to create an Iterator for the linked list, which will allow the user to iterate over the list, sequentially in one direction, in \(O(n)\) time.
Write a new method of your linked list class
called iterator(). This method takes no parameters.
It returns a LinkedListIterator object, which can be
used to iterate over the elements of the list.
In addition to this new method, you need to implement
the LinkedListIterator class. It is ok to write this
code in the same file as your LinkedList class. This class must(!)
define at least two methods:
bool hasNext(), which returns true if there is more
data to be printed by the iterator.
int next(), which returns the next piece of data
from the iterator.
Make sure you test your methods carefully. Think about what the edge cases are, and how to handle them appropriately.
Uncomment the testIterator function definition and calls