Lab 3   Circular Linked Lists and the Josephus problem

This lab is an exercise in the implementation of linked lists.  We will look at the implementation of a circular linked list, which is a modification of the node-based list introduced in class.  Then we will use the implementation to solve a problem called the Josephus problem.

You can get started by creating a lab3 directory and downloading this week's jar file lab3.jar .  It contains an interface called SimpleList, which is a subset of Java's List interface.  It also contains the LinkedList class from yesterday's lecture.

Your tasks in this lab are to:

• Create a CircularLinkedList class by modifying LinkedList.java.
• Test out the CircularLinkedList class.
• Write an application program based on the Josephus problem.
• Write an append method for CircularLinkedLists.
• Use your CircularLinkedList class to write a radix sort algorithm.
  

Part One.  Writing the CircularLinkedList class.

In the linked list implementation we studied in class, the last node in each list contained a null reference, to indicate that there were no more elements in the list.  An alternative is to let the last node contain a reference to the first node, thus making a circle of all the nodes.  This is called a circular linked list.  To reference a circular linked list, one needs only a reference to the tail node; the head can easily be located through tail.next.  The picture below shows a circular linked list containing four data items, A, B, C, and D:



Your job here is to modify the LinkedList class to make it into a circular linked list.  Start by copying LinkedList.java to CircularLinkedList.java.  Make the following changes:

1.    Change the class name to CircularLinkedList.  You'll also need to change the name of each constructor to CircularLinkedList.
2.    Modify the constructors.  In an empty CircularLinkedList, nitems is 0 and the tail reference is null.  A CircularLinkedList with one node should look like this:



3.    Now modify the remaining methods.  Some of the existing code will work with the new structure, but some will have to be changed.  Remember that you no longer have a reference to the head of the list.  Also remember that you need to make sure after each operation is completed that the next field in the tail node contains a reference to the head of the list.

Note:  Do not modify the ListNode class!


Part Two.  Some testing.

Test out your CircularLinkedList class, by writing some simple applications.  Each of these should be written as a main program in a separate .java file.

1.    Take an array of Strings from the command line and insert them one-by-one into a CircularLinkedList, using the add(Object) method.  Then print the contents of the list.

(Note:  The main program header should be written

static public void main(String[] args)

args is an array of Strings containing the words entered by the user on the command line.)

2.    Same as #1, but insert each String at the beginning of the list, using the add(int index, Object obj) method.
3.    Same as #1, but insert each String at the midpoint of the list.
4.    Take an array of Strings from the command line and insert them one-by-one into a CircularLinkedList.  Remove every element at an even position in the list.  Then print the contents of the list.
5.    Same as #4, but remove the elements at the odd positions.


Part Three.  The Josephus problem.

Background

Josephus Flavius was a famous Jewish historian of the first century at the time of the Second Temple destruction.  During the Jewish-Roman war he got trapped in a cave with a group of 39 soldiers surrounded by Romans.  The legend has it that preferring suicide to capture, the Jews decided to form a circle and, proceeding clockwise around it, to kill every seventh person until only one was left, who must then commit suicide.  Josephus, an accomplished mathematician, quickly found the safe spot in the circle (24th) to be the last to go.  But when the time came, instead of killing himself he joined the Roman side.  The problem rightfully raises the question of how someone might be able to quickly compute the correct place to stand.

In this lab you are to simulate the Josephus problem.  Your program will be written as a main program in the file Josephus.java.  The program command line contains an integer n representing the elimination order, followed by a list of names; for example,

java Josephus 3 Andrea Peter Phil Michael Joanna Aaron Akshat Alexander Brandon Arthur

The program should simulate the Josephus problem by repeatedly removing the nth name from the list and displaying it.  At the end, display the name of the survivor.  For the example above, your output should be:

Phil
Aaron
Brandon
Peter
Akshat
Andrea
Alexander
Joanna
Arthur

The survivor is Michael.

It is possible to write this program with the existing methods in CircularLinkedList.java.  However, you can write a nicer version which makes use of the circular link to simulate the circle of people.  Add the following method:

Object removeAndRotate(int index);

removeAndRotate has the same semantics as remove, with the following changes:

1.    index may be any nonnegative integer.  To remove the 37th element from a list of 10, just following the links 37 times and remove that element.  (This is equivalent to removing the 7th element.)
2.    After the removal, move the tail pointer so that it points to the element just prior to the one which was removed.  The effect of this is that in successive calls to remove, each one resumes where the previous one finished.  This is consistent with how a simulation of the Josephus problem should work.

Your program for the Josephus problem should work by making successive calls to removeAndRotate.

Part Four.  Another operation which can be implemented easily with circular linked lists is the "append" operation, which attaches the contents of one linked list to the end of another.  It can be accomplished by letting the tail pointer of the first list point to the head of the second list.

Write an append method in CircularLinkedList.java as follows:

    void append(CircularLinkedList other);

It attaches "other" to the end of "this" list and returns a reference to this list.

Also write a simple application to test your method.


Part Five.  Radix sort.

Radix sort is a sorting method which works by testing the digits of a multidigit number, one at a time, from right to left.  Several passes are made over the data, one for each digit.  On each pass, the numbers are thrown into bins, with one bin for each possible digit.  (In base 10, there would be 10 bins.)  After the all the numbers are distributed into the bins, the contents of the bins are combined into a single list.

Thus the algorithm works like this to sort a list of n-digit numbers, using radix r:

for digitPosition = 0 to n-1 { // numbering is right-to-left
    create r empty lists numbered 0 through r-1;
    for each number in the list {
        let d be the digit of the number at digitPosition;
        add the number to list d;  // it must be added at the end of the list
    }
    append the r lists into one; //  they must be appended in order from list 0 through list r-1
}

The resulting list is sorted in increasing order.

Write an application called RadixSort.java which takes one command-line argument n, and does the following:

1.    It creates a CircularLinkedList of n 6-digit integers chosen at random.
2.    It prints the contents of the list.
3.    It sorts the list using the radix sort algorithm.
4.    It prints the contents of the sorted list.

Notes:

1.    The kth digit of a base 10 number (with digits numbered right-to-left) can be obtained by

digit = ( number / 10^k ) % 10;

2.    Because "int" is a primitive type, you cannot store "int"s in a list of Objects.  To do so, you need to use the Integer "wrapper class".  An Integer object can be constructed from an int using its constructor; for example to create an Integer object with the value 500, one could write

Integer iObject = new Integer(500);

To convert an Integer back to an int, use its "intValue" method:

int n = iObject.intValue();