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

• Adding an entry to or removing an entry from an array-based list typically requires that other entries shift by

one position within the array. This data movement degrades the time efficiency of these operations, particu-
larly when the list is long and the position of the addition or removal is near the beginning of the list.

•

Expanding the size of an array adds to the time required by the affected add method, since doing so requires
copying the contents of the array to a larger array.

•

Using an instance of java.util.Vector has the same advantages and disadvantages as using a resizable array
but results in an implementation that is much easier to write.

E XERCISES

1.

Add a constructor to each of the classes AList and VectorList that creates a list from a given array of objects.

2.

Suppose that you want an operation for the ADT list that returns the position of a given object in the list. The
header of the method could be as follows:
public int getPosition(T anObject)
where T is the generic type of the objects in the list. Write an implemention of this method for each of the two
classes described in this chapter.

3.

Suppose that you want an operation for the ADT list that removes the first occurrence of a given object from the
list. The header of the method could be as follows:
public boolean remove(T anObject)
where T is the generic type of the objects in the list. The method returns true if the list contained anObject and that
object was removed. Write an implementation of this method for each of the two classes described in this chapter.

4.

Suppose that you want an operation for the ADT list that moves the first item in the list to the end of the list. The
header of the method could be as follows:
public void moveToEnd()
Write an implemention of this method for each of the two classes described in this chapter.

5.

Exercise 8 in the previous chapter asked you to write statements at the client level that replace an object in a given
list. Write a method at the client level that performs such a replacement. How does your method compare with the
method replace of the ADT list?

6.

The method replace for the ADT list returns a boolean value. Implement a method replace that returns the
replaced object. Do this for each of the two classes described in this chapter.

7.

Suppose that a list contains Comparable objects. Implement the following methods for each of the two classes
described in this chapter:
/** Returns the smallest object in the list. */
public T getMin()
/** Removes and returns the smallest object in the list. */
public T removeMin()

8.

Implement an equals method for the ADT list that returns true when the entries in one list equal the entries in a
second list. In particular, add this method to the classes AList and VectorList .

9.

Repeat the previous exercise, but have the equals method call a private recursive method that detects equality.

10.

Consider the method contains in the class AList . Revise the method's definition so that it calls a private recur-
sive method that detects whether the list contains the given object.

11.

Implement the methods contains , getLength , and isEmpty in the class VectorList .