• Implement a circular linked list
• Use the circular list to solve a problem

This assignment is based on the Programming Projects 4 and 5 in Chapter 2 on p. 145.

Implement a CircularList Class (Exercise 4):

Complete the design and implementation of a generic circular list with a single-linked list. Note that as stated in the exercise, a circular list doesn't have a first or last node. It just needs a reference to a current node. This is similar to a reference to the last node of a regular linked list.

Examples:

Empty list	One element list
Three element list

The nature of the circular list is a bit different than the normal list because of not having a first or last element. Notice that none of the methods have an index parameter, since there isn't any notion of a position in a circular list.

The structure of this class is shown in the following UML diagram:

The public methods to be implemented are add - inserts a new element at the current position (the newly added element becomes the current) get - returns a reference to the contents of the node at the current position size - returns the number of elements in the list iterator - returns an Iterator for the list     The iterator method must implement the Java Iterator interface, including the remove method. Take note of Iterator's method specifications here, particularly for the remove method. As stated in the exercise, the hasNext method will always return true unless the list is empty.

Circular list iterator

The need for a remove method complicates the implementation of the lterator. Recall that any modifications to a single-linked list require a reference to the node preceding the point where the modification is to occur. This means that to remove the last element returned by next, it will be necessary to have a reference to the node two positions behind.

Be careful with the remove method. Note that it is supposed to be called only after calling next. So if remove is called a second time, the next needs to be called again first. Also if the current node is removed then the current reference needs to be reassigned or whole list will be lost! Think about which node current always points to -- the "oldest" node in the list. Make sure that this is still true after the current node is deleted.

It would be a good idea to test the methods of this class during implementation with JUnit.

The Josephus Problem (Exercise 5):

Write an application that uses the circular list class to solve the Josephus problem described in exercise 5. (If you find this too morbid, you can think of it as being like musical chairs.)

The program should prompt the user for the number of people and the number of counts.

The output of the program should be a listing of the positions removed from the list and which position is the last one left.

Use the iterator for the circular list class to traverse the list and remove elements.

Extra credit (Exercise 6):

Do the enhanced and historically accurate version of the Josephus problem as described in exercise 6.

Hand in:

Submit all of your source code files.