List Implementations That Use Arrays - Data Structures and Abstractions with Java - page 333

12.

The class AList has an array that can grow in size as objects are added to the list. Consider a similar class whose
array also can shrink in size as objects are removed from the list. Accomplishing this task will require two new
private methods.
The first new method checks whether we should reduce the size of the array:
private boolean isTooBig()
This method returns true if the number of entries in the list is less than half the size of the array and the size of the
array is greater than 20.
The second new method creates a new array that is three quarters the size of the current array and then copies
the objects in the list to the new array:
private void reduceArray()
Implement each of these two methods for our new class. Then use these methods in the definition of the method remove .

13.

Consider the two private methods described in the previous question.
a. The method isTooBig requires the size of array to be greater than 20. What problem could occur if this
requirement is dropped?
b. The method reduceArray is not analogous to the method ensureCapacity in that it does not reduce the size of
the array by one half. What problem could occur if the size of the array is reduced by half instead of three quarters?

P ROJECTS

1.

Write a program that thoroughly tests the class AList . Next, revise your program to perform the same tests on the
class VectorList .

2.

Define a class of bags by using an instance of the class AList to contain its entries. Then write a program that ade-
quately demonstrates your new class.

3.

Repeat Project 2, but define a class of stacks instead.

4.

Repeat Project 2, but define a class of queues instead.

5.

Repeat Project 2, but define a class of deques instead.

6.

Repeat Project 2, but define a class of sets instead. Recall from Project 1 in Chapter 1 that a set is a bag whose
entries are distinct.

7.

Implement the interface ListInterface by using an array in which you ignore the first array location. Thus, you
store the list's i th entry in the array location at index i .

8.

Using a fixed-size array to implement the ADT list limits the size of the list. Some applications can use a list that
has a limited length. For example, the length of a list of airline passengers or a list of ticket holders to a movie
should not exceed a known maximum.
Define an interface FixedSizeListInterface that is similar to ListInterface , but adds the method isFull and
revises the specifications of other methods as necessary to accommodate a fixed-size list. Consider whether your new inter-
face should extend ListInterface . Then define and demonstrate a class that implements FixedSizeListInterface .

9.

Implement as the class Shoe the ADT shoe that Project 4 of Chapter 1 describes. Hint : To shuffle the shoe, use two
private lists of cards, a source list and a shuffled list. Put all the available cards into the source list. Initially, this will
be every card. Later, only those cards not held by a player will be available. Use the class java.util.Random to
repeatedly generate a random position in the source list, remove the card at that position, and put it at the end of the
shuffled list.
Write a program that adequately demonstrates the operation of the class Shoe .

10.

Implement the ADT bid that Project 5 of Chapter 1 describes.

11.

Implement the ADT for the objects in Santa's nice list that Project 6 of Chapter 12 describes. Then create some
instances of your class and place them on the nice list.