Josephus Problem

Your task is to create a GUI program that will simulate the Josephus Problem. The user should have the ability to input a list type (DoubleLinkedList or ArrayList), the initial length of the circle, and the count amount. The program then should output the last person standing along with the amount of time (in milliseconds) it took to determine this answer. If you want, you could optionally display the numbers as they die.

For this project, you will create a class called DoubleLinkedList that is started below. You will notice that this class inherits from AbstractSequentialList. The AbstractSequentialList class provides a skeleton implementation of Java's List interface which minimizes the amount of effort required to implement the List interface. All you have to do, in fact, is inherit from AbstractSequentialList and provide the implementation for the listIterator() and size() methods, and as a result, you will have a fully functional List that can perform any and all methods in the Java List's interface. How does this work? The AbstractSequentialList simply utilizes the methods of the listIterator to implement the List methods.

In order to implement the listIterator() method, you must complete the ListIter inner class. This class implements the ListIterator interface. Please be sure to take a look at the ListIterator interface on the API before you implement this inner class to ensure you address all the requirements.

import java.util.AbstractSequentialList;
import java.util.ListIterator;
 
public class DoubleLinkedList<E> extends AbstractSequentialList<E>
{
    private Node<E> head;
    private Node<E> tail;
    private int size = 0;
 
    /**
     * The inner class which represents a Node
     */
    private static class Node<E> 
    {    
        private E data;
        private Node<E> prev;
        private Node<E> next;
 
        private Node(E dataItem)  
        {
            data = dataItem;
            prev = null;
            next = null;
        }
 
        private Node(E dataItem, Node<E> p, Node<E> n) 
        {
            data = dataItem;
            prev = p;
            next = n;
        }
    }
 
    /**
     * The inner class which implements the ListIterator
     */
    private class ListIter implements ListIterator<E>
    {
        private Node<E> nextItem;
        private Node<E> lastItemReturned;
        private int index;
 
        /** 
         *    Constructs a ListIter.
         */
        public ListIter() 
        {
            lastItemReturned = null;
            nextItem = head;
            index = 0;
        }
 
        /** 
         *    Adds a new item between the item that will be returned
         *    by next and the item that will be returned by previous.
         *    If previous is called after add, the element added is
         *    returned.
         *    @param obj The item to be inserted
         */
        public void add(E obj) 
        {
 
        }
 
        /** 
         *    Indicates whether movement forwards is possible.
         *    @return true if movement forward is possible.
         */
        public boolean hasNext() 
        {
 
        }
 
        /** 
         *    Indicates whether movement backward is possible.
         *    @return true if movement backward is possible.
         */
        public boolean hasPrevious()
        {
 
        }
 
        /** 
         *    Moves the iterator forward and returns the next item.
         *    @return the next item in the list
         *    @throws NoSuchElementException if there is no such object
         */
        public E next() 
        {
 
        }
 
        /** 
         *    Returns the index of the element that would be returned
         *    by a subsequent call to next.
         *    @return the index of the next element to be returned when next is called.
         */        
        public int nextIndex() 
        {
 
        }
 
        /** 
         *    Moves the iterator backward and returns the previous item.
         *    @return The previous item in the list
         *    @throws NoSuchElementException if there is no such object
         */
        public E previous() 
        {
 
        }
 
        /** 
         *    Returns the index of the element that would be returned
         *    by a subsequent call to previous.
         *    @return the index of the next element to be returned when prev is called.
         */    
        public int previousIndex() 
        {
 
        }
 
        /** 
         *    Removes the node referenced by lastItemReturned
         *    @return item removed
         *    @throws IllegalStateException if called without calling 
         *    next or previous before.
         */
        public void remove()
        {
 
        }
 
        /**
         *    Replaces the lastItemReturned from a call to next
         *    or previous with obj
         *    @param obj the new value for node
         *    @return the old value
         *    @throws IllegalStateException if called without calling
         *    next or previous before.
        */
        public void set(E obj)
        {
 
        }
    }
 
    /**
     * Constructor for the DoubleLinkedList
     */
    public DoubleLinkedList()
    {
 
    }
 
    /**
     * Returns the size of the list
     * @return the size of the list
     */
    public int size()
    {
 
    }
 
    /**
     * Returns a list iterator over the elements in this list (in proper sequence).
     * @return the list iterator over the elements in this list. 
     */
    public ListIterator<E> listIterator()
    {
 
    }
 
    /**
     * Returns a list iterator over the elements in this list (in proper sequence)
     * starting at the index number passed in.
     * @return the list iterator over the elements in this list starting at the index
     * number passed in. 
     */
    public ListIterator<E> listIterator(int index) 
    {
 
    }
}

Once you have your DoubleLinkedList class completed, be sure to test it thoroughly to ensure it is functioning correctly. You can verify this by comparing it against a listIterator of an ArrayList. Below is sample code that uses the listIterator from an ArrayList.

ArrayList<Integer> list = new ArrayList<Integer>();
list.add(5);
list.add(10);
 
ListIterator<Integer> itr = list.listIterator();
System.out.println(itr.next());
System.out.println(itr.previous());
System.out.println(itr.next());
System.out.println(itr.previous());
 
System.out.println(itr.next());
System.out.println(itr.next());

Now that we have a DoubleLinkedList class that inherits from AbstractSequentialList (which implements the List interface), we can create more generic code as illustrated below:

List<Integer> myList;
myList = new DoubleLinkedList<Integer>();
myList = new ArrayList<Integer>();

The point is that I can easily switch between DoubleLinkedList and ArrayList in my program now since they both implement the List interface. This is very powerful!