Lab 2   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 in two applications:  the Josephus problem and the radix sort.

You can get started by creating a lab2 directory and downloading this week's jar file lab2.jar .  It contains the LinkedList class that we wrote in class.  Note that LinkedList is an implementation of an interface called SimpleList.  SimpleList contains a subset of the methods of the List interface from the java.util package.  The source code for SimpleList is also found in the lab2 jar file.

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.  (However, you can locate the head node by following the next field in the tail node.)  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 a main program which performs some simple list manipulations.  The program should do the following:

1.    Take the array of Strings from the command line and insert them one-by-one into a new 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.    Instantiate another CircularLinkedList.  Insert each String from the command line at the beginning of the list, using the add(int index, Object obj) method.  Then print the contents of the list.

3.    Instantiate another CircularLinkedList.  Insert each String from the command line at the midpoint of the list, then print the contents of the list.

4.    Use the list you created in step 1.  Remove every other element from the list, starting with the 0th element.  Then print the contents of the list.


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 was 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 7 Steven Abigail Ivan Scott NicholasF Naomi Matthew Leah NicholasH Ryan Lidiya Megan Richard Brendan NicholasW

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:

Matthew
Brendan
Naomi
NicholasW
NicholasH
Ivan
Richard
Lidiya
Ryan
Megan
Abigail
Leah
Steven
Scott

The survivor is NicholasF.

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.

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 nonnegative 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 (numbering the digits 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();