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

public static Node playGame(Node last, int x, int m) {
//Eliminate x children with countout length of m;
//last points to the last child which points to the first child
Node prev = last, curr = last.next; //curr points to first child
//eliminate x children
for (int h = 1; h <= x; h++) {
//curr is pointing at the first child to be counted;
//count m-1 more to get to the mth child
for (int c = 1; c < m; c++) {
prev = curr;
curr = curr.next;
}
//delete the mth child
prev.next = curr.next;
curr = prev.next; //set curr to the child after the one eliminated
}
return curr;
} //end playGame
} //end class CountOut
class Node {
int num;
Node next;
public Node(int n) {
num = n;
next = null;
}
} //end class Node
The following is a sample run of Program P3.7:
Enter number of children and length of count-out: 9 10
The winning child: 8
3.16.2 Two-Way (Doubly Linked) Lists
As the name implies, each node will contain two pointers; one points to the next node, and the other points to the
previous node. While this requires more work to implement and maintain, there are some advantages.
The obvious one is that it is now possible to traverse the list in both directions, starting from either end.
If required, reversing the list is now a simple operation.
If we land at a node (the current node) in a singly linked list, there is no way to get to (or know) the previous node
unless that information was kept as the list was traversed. With a doubly linked list, we have a direct pointer to the
previous node so we can move in either direction.
One possible disadvantage is that more storage is required for the extra link. Another is that adding and deleting
nodes is more complicated since more pointers have to be set.