Linked Lists - Building Java Programs: A Back to Basics Approach - page 977

doubly linked list. The methods to add are the following (see the Java API Specification for descriptions of
each method):
• public void add(E value)
• public boolean hasPrevious()
• public int nextIndex()
• public E previous()
• public int previousIndex()
• public void set(E value)
3. The implementation of several methods is (or can be) the same between our ArrayList and LinkedList . Write a
common abstract superclass called AbstractList that implements the common behavior and is extended by both
ArrayList and LinkedList . Factor out the common code from the two list classes into this abstract superclass so
that no code duplication occurs between the two. Use iterators wherever possible in the abstract code to ensure that
the implementation is efficient for both types of lists.

4. “Assassin” is a real-life game in which a group of players all try individually to find and touch (or “kill”) one other
player. You can use a linked list to represent this “kill ring” of players in the game:

front Joe Sally Jim Carol Chris

If a “kill” is made, the ring adjusts by removing that person from the list. For example, the following occurs if Sally
kills Jim:

front Joe Sally Jim Carol Chris

Write a program that models a game of Assassin. The game reads the names of the initial kill ring from a file and puts
them into a linked list in random order. Then the game repeatedly prompts for the name of a person has been killed.
The game continues until only one player remains and is declared the winner. The program should also have methods
for printing the current contents of the kill ring and printing a “graveyard” of all players who have been killed.

5. Write a graphical program that shows a set of overlapping rectangular regions, each in a different random color. The
regions are represented internally as a linked list. The regions have a “ z -ordering” in which rectangles closer to the
end of the list are closer to the top, closer to the user's field of view. When the user clicks the mouse, the topmost
region that touches the mouse pointer moves to the very top (end) of the linked list. For example, the following dia-
grams show the top-left rectangle before and after the mouse is clicked:

(See the Nifty Assignments page at http://nifty.stanford.edu for a more detailed description of this project, as written
by its original author, Prof. Michael Clancy of the University of California, Berkeley.)