CSC148H lab -- week 8

Here are the instructions for the week 8 CSC148H lab. To earn your lab mark, you must actively participate in the lab. As always, you will work as a pair, taking turns being the driver and the navigator. The driver types, and the navigator watches for mistakes, thinking ahead. At the end of each exercise, show your TA what you've done, and then switch roles.

This week's exercises are on the topic of iterators.

We're not using generics

We don't want to focus this lab on the proper use of generic type parameters, even though the classes you use and write here are a natural example where generics would be useful. You'll find a comment on this in one of the classes, and you might like to consider how to do this -- or even, if you're reasonably familiar with generics, work through revising all the code on your own.

Exercise 1: Using an Iterator

When it's your first turn as driver, begin by making a new folder "lab8". In lab8, save the files that we've provided for you: LinkedNode.java, LinkedList.java and Driver.java.

1. Quickly read the code for classes LinkedNode and LinkedList. Notice that the iterator() method in the class LinkedList is not implemented yet; you will change this later.
2. Write the body of the main() method in class Driver, following the directions given in the comments in main().
3. Compile the code. It will not run yet, but make sure that it compiles successfully.

Exercise 2: Implementing the Iterator interface

1. Write a new class LinkedIterator to implement the Iterator interface for the LinkedList class.
   • Read the API documentation for interface Iterator to refresh your memory.
   • Make sure that you import java.util.*; at the top of your file (or you won't be able to use Iterator).
   • Do not implement method remove(); that is, write a body for the method that only throws a new UnsupportedOperationException. (See the iterator() method in class LinkedList for an example.)
   • Similarly, see the removeLast() method in class LinkedList for an example of throwing a NoSuchElementException when next() is called with no list items left to return.
   • Think carefully about the information that an instance of LinkedIterator must keep track of in order to be able to traverse the elements in a LinkedList one by one. Discuss this with your partner and make sure that you agree on the details.
   • Remember that instances of LinkedIterator will always be created from inside an instance of LinkedList: think carefully about the information that must be given to the LinkedIterator by the LinkedList and write an appropriate constructor for class LinkedIterator.
2. Write the body of method iterator() in class LinkedList. (Remove the line "throw ...".)
   (Hint: You only need one line of code.)
3. Compile and run your program to make sure everything works.

Exercise 3: Testing your implemention

1. Discuss appropriate test cases to thoroughly test your implementation of the Iterator interface. You do not need a large number of cases.
2. Run your test cases using the code you've already written.

Exercise 4: Writing a second kind of Iterator

1. Based on the work you've done already, add code where appropriate to be able to iterate over the elements of a LinkedList in the reverse direction (from the last element to the first).
   
   This will involve creating a new class, adding a new method to the LinkedList class, and adding code to the main() method to test your implementation.