Pls read the instruction carefully.

Carefully read the entire document before you start coding. You are required to implement the LinkedList data structure without using any readily available classes or interfaces in Java.

1 Overview In this homework, some code is already given to you. Your task is to write additional code based on what is given. The provided code is as follows, with interfaces in green, and classes in blue: MyCollection MyList MyLinkedList All interface methods are completely documented in the provided code, and most class methods in MyLinkedList are documented as well. Your task consists of 1. completing the incomplete methods in the MyLinkedList class. Make sure that your imple- mentation of these methods stays true to the rules specified in the documentation, 2. write your own special kind of circular linked list where the last element refers back to the first element of the list, and 3. use this circular linked list to solve the Josephus Problem. 2 Tasks 1. (16) Completing the linked list data structure This is given to you as the MyLinkedList class. For this part of the assignment, you are not allowed to change any given code, except for the parts explicitly marked with the TODO comment. You can, however, add your own getter and setter methods for any of the fields in this class. Pay close attention to the iterator class created here, called MyLinkedListIterator. This inner class has already been completed, and you dont have to do anything here. But understanding how the iterator class works may prove important in using the circular list later! It is important to understand how iterators work. Java has a generic interface called Iterable, and any class over which you may want to write standard iteration code (e.g., enhanced for loops) must implement this interface.

Writing the circular linked list In this second component of the assignment, you must write a class called CircularList with the following signature (do NOT change this signature) public class CircularList extends MyLinkedList You will have to carefully decide what methods from MyLinkedList you want to override in the circular list. The overall idea is that this list is circular in the sense that the last nodes next refers back to the very first node (i.e., head) of the list. This means that, in particular, you will have to write a circular iterator for this class. 3. (20) Hot Potato! The childrens game of hot potato is a more innocent version of the ancient Josephus Problem, where a group of soldiers took turn to commit suicide in favor of surrendering to the enemy. You can read more about the problems history here https://en.wikipedia.org/wiki/Josephus_problem#History. The problem (or rather, game) is as follows: N people, numbered from 1 to n, are sitting in a circle. Starting at person 1, a hot potato is passed. After m passes, the person holding the hot potato is eliminated, the circle closes ranks, and the game continues with the next person who was sitting after the eliminated person picking up the hot potato. The last person to remain, wins the game. For example, If m = 0,n = 5, players are eliminated in order, and player 5 wins. If m = 1,n = 5, players are eliminated in the order 2,4,1,5. Your task is to write a Java class called HotPotato to solve the Josephus problem for general values of m and n. That is, your class should look like public class HotPotato { ... public HotPotato(int m, int n) { // constructor code } public void play() { ... } } You have almost complete freedom in writing this class, but the following rules must be followed: The class must have a generic type parameter. The constructor signature must be as shown above. The class must have a method public void play(). Invoking this method will play the actual game until there is only one person remaining. The play method must print, at every elimination, the following information (in this format, with a blank line separating every elimination stage): > Eliminated person: ... > Remaining circle (starting with the next person): ... > > Eliminated person: ... > Remaining circle (starting with the next person): ... > . . . > Winner: ... We have left the actual person information as ... because the class is generic, which means that the game can be played with numbers (i.e., type Integer), names (i.e., type String, a custom class called Person (i.e., type Person), etc. To solve the problem, you must implement the circle using the circular linked list class you wrote. The eliminated player must be removed from the list. Simply skipping that person when printing the games steps is not acceptable. You will not get any points for the game implementation if you do this. 3 Guidelines Can I change the given code? No. You can (and must, where specified) add your code, but you cannot modify any existing code.