Linked Lists - Advanced Topics in Java: Core Concepts in Data Structures - page 104

This loop will never terminate since curr never becomes null . To avoid this problem, we can save the pointer of
our starting node and recognize when we have returned to this node. Here's an example:

Node curr = top;
do {
//do something with node pointed to by curr
curr = curr.next;
} while (curr != top) {

Alert readers will observe that since the body of a do...while loop is executed at least once, we should ensure
that the list is not empty before going into the loop and trying to dereference a null pointer.
Circular lists are useful for representing situations that are, well, circular. For example, in a card or board game in
which players take turns, we can represent the order of play using a circular list. If there are four players, they will play
in the order 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, and so on. After the last person plays, it's the turn of the first.
In the children's game count-out , the children are arranged in a circle and some variation of “eenie, meenie,
mynie, mo; sorry, child, you've got to go” is used to eliminate one child at a time. The last remaining child wins the
game.
We will write a program that uses a circular list to find the winner of the game described as follows:

The count-out game : n children (numbered 1 to n ) are arranged in a circle. A sentence consisting of m words is
used to eliminate one child at a time until one child is left. Starting at child 1, the children are counted from 1 to m and
the m th child is eliminated. Starting with the child after the one just eliminated, the children are again counted from 1
to m and the m th child is eliminated. This is repeated until one child is left. Counting is done circularly, and eliminated
children are not counted. Write a program to read values for n and m (> 0), play the game as described, and print the
number of the last remaining child.
It is possible to use an array ( child , say) to solve this problem. To declare the array, we would need to know the
maximum number ( max , say) of children to cater for. We could set child[1] to child[n] to 1 to indicate that all n
children are initially in the game. When a child ( h , say) is eliminated, we would set child[h] to 0 and start counting
out from the next child still in the game.
As the game progresses, several entries in child will be set to 0 , and when we count, we must ensure that 0 s are
not counted. In other words, even when a child has been eliminated, we must still inspect the array item and skip it if
0 . As more children are eliminated, we will need to inspect and skip more zero entries. This is the main disadvantage
of using an array to solve this problem.
We can write a more efficient solution using a circular linked list. First, we create the list with n nodes. The value
at each node is the child's number. For n = 4, the list will look like the following, assuming curr points to the first child:

curr

1 2 3 4

Suppose m = 5. We start counting from 1; when we reach 4, the count of 5 takes us back to child 1, which is
eliminated. The list will look like this:

curr

1 2 3 4