ICS 211 Homework A04: Implement ListIterators for both the ArrayList and DoubleLinkedList Classes.

Part 1: Add ListIterator to your MyArrayList and MyLinkedList classes

Modify your MyArrayList and MyLinkedList classes from the previous two assignments to include a ListIterator. Use the following ListIterator interface:

public interface ListIterator<E> {
  boolean hasNext(); // Returns true if this list iterator has more elements while traversing in the forward direction.
  boolean hasPrevious(); // Returns true if this list iterator has more elements while traversing in the reverse direction.
  E next(); // Returns the next Element.
  int nextIndex(); // Returns the index of the next element.
  E previous(); // Returns the previous Element
  int previousIndex(); // Returns the index of the previous element.
}

Part 2: Modify your MyArrayList and MyLinked list to implement the Iterable interface.

Using your ListIterator implementations, update your MyArrayList and MyLinkedList classes so that they implemement the *Iterable* interface. Demonstrate this by printing out the elements in your lists using the *foreach* Java for loop.

List<Contact> list;  // Use both your MyArrayList and MyLinkedList
for (Contact c: list) {
  System.out.println(c);
}

Testing

Please thoroughly test your code and briefly discuss your testing strategy. Make sure that you test the different sorting algorithms. Turn in all your test code.

Turning in the Assignment

The assignment is due on Friday at 11:55pm. You may turn it in early.

1. Conduct a personal review of your code before turning it in. Does you code follow the Java Coding Standard? Is it clear and well commented?
2. Test your code.
3. Sign into Laulima, then navigate to the ICS211 site. In the left hand side of the site, there is an Assignments tab/link. Click on it and view all of the posted assignments. Select the assignment that you want to turn in and attach your files and accept the honor pledge to submit the assignment.

Extra credit: Josephus Problem

Description

The Josephus problem is named after Flavius Josephus, a historian and a reluctant leader of a revolt against the Roman Empire. When it appeared Josephus and his band were about to be captured, they chose to commit suicide rather than be enslaved. It is believed that the procedure they followed was for everyone in his band to form a circle and starting in a given direction, at a certain band member, count around the circle a predetermined number. When this number is reached, the person leaves the circle and commits suicide. The circle shrinks as the counting continues. When a person drops out of the circle, the count starts over with the next person.

Implement a simulation of the Josephus Problem, using the ListIterator Interface above and a Circular Double-Linked List. Use a set of test data to thoroughly test your simulation.

Josephus Class

• Create a class Josephus which uses a CircularDoubleLinkedList. The class should have the following method.

 
  /**
   * Returns a LinkedList<Integer> of the people in the order they were removed.
   * @param size - number of people in circle
   * @param start - the position of where to start counting from
   * @param step - predetermined number for counting off
   * @param isClockwise - if isClockwise is true, counting occurs in a
   * clockwise manner. If isClockwise is not true, then counting occurs
   * in a counter-clockwise manner.
   * @return LinkedList<Integer> of the indexes of the people as they were removed.
   */
  LinkedList<Integer> testList(int size, int start, int step, boolean isClockwise) {
    // your code
  }

Feel free to implement other methods in any of the classes which will help solve this problem.

Example

  testList(7, 1, 3, true);

There are seven members in the band, numbered 1 through 7, and you start at 1 and count off by threes in a clockwise direction. Band members will be eliminated in the order 3, 6, 2, 7, 5, 1. In this example, the band member at position number 4 will remain at last