CONCEPT EXERCISES
6.1 State two advantages, and one disadvantage, of using an ArrayList object instead of an array object. Get the solution of 6.1
6.2 Show that, for the task of appending n elements to an ArrayList object, worstTime(n) is linear in n. Get the solution of 6.2
6.3 The one-parameter add method in the ArrayList class always returns true. Would it make sense to change the return type from boolean to void ? Explain. Get the solution of 6.3
6.4 For the one-parameter add method in the ArrayList class, estimate worstSpace(n) and averageSpace(n). Get the solution of 6.4
6.5 In choosing fields for the VeryLongInt class, we decided to use, rather than inherit from, the ArrayList class. Why?
Hint: How much commonality is there between the methods in the ArrayList class and the methods in the VeryLongInt class? Get the solution of 6.5
6.6 Suppose you modified the VeryLongInt class as follows: each element in digits consists of a five-digit integer. What effect do you think this will have on Big-O time? What about run-time? Get the solution of 6.6
6.7 Suppose, in developing the VeryLongInt class, we decide that digits will contain the integer in reverse order. For example, if the constructor call is:
VeryLongInt veryLong = new VeryLongInt ("386");
we would have (Integer elements with values) 6, 8, 3 in positions 0 through 2, respectively of digits.
Re-design this constructor so that worstTime(n) is still linear in n. Get the solution of 6.7
6.8 Which parts of the VeryLongInt methods would have to be re-written if digits were an array object of int elements instead of an ArrayList object of Integer elements? Get the solution of 6.8
6.9 How can a user of the VeryLongInt class easily create a VeryLongInt object that is a copy of an already existing VeryLongInt object? Get the solution of 6.9
PROGRAMMING EXERCISES
6.1 Hypothesize the output from the following code, and then test your hypothesis with a small program that includes the code:
ArrayList<String> letters = new ArrayList<String>();
letters.add ("f");
letters.add (1, "i");
letters.add ("e");
letters.add (1, "r");
letters.add ("e");
letters.add (4, "z");
System.out.println (letters);
letters.remove ("i");
int index = letters.indexOf ("e");
letters.remove (index);
letters.add (2, "o");
System.out.println (letters); Get the solution of 6.1
6.2 For each of the following program segments, hypothesize if the segment would generate a compile-time error, a run-time exception, or neither. Then test your hypotheses with a main method that includes each segment.
a. ArrayList<String> myList = new ArrayList<String>();
myList.add ("yes");
myList.add (7);
b. ArrayList<Double> original = new ArrayList<Double>();
original.add (7);
c. ArrayList<Integer> original = new ArrayList<Integer>();
double x = 7;
original.add (x);
d. ArrayList<String> newList = new ArrayList<String>();
newList.add ("yes");
Integer answer = (Integer)newList.get (0); Get the solution of 6.2
6.3 Suppose we have the following code:
ArrayList<String> myList = new ArrayList<String>();
myList.add ("Karen");
myList.add ("Don");
myList.add ("Mark");
ArrayList<String> temp = new ArrayList<String> (myList);
ArrayList<String> sameList = myList;
myList.add (1, "Courtney");
Hypothesize what the contents of myList, temp, and sameList will be after this last insertion. Then test your hypothesis with a main method that includes the code. Get the solution of 6.3
6.4 Hypothesize what will happen when the following code fragment is run, and then test your hypothesis:
ArrayList<String> original = new ArrayList<String>();
original.add ("yes");
ArrayList<Integer> copy = (ArrayList<Integer>)original.clone();
System.out.println (copy.get (0));
Hint: This exercise illustrates why the copy constructor is superior to the clone() method. Get the solution of 6.4
6.5 Expand the VeryLongInt class by testing and defining methods that have the following method specifications:
a. /**
* Initializes this VeryLongInt object from a given int.
*
* @param n – the int from which this VeryLongInt is initialized.
*
* @throws IllegalArgumentException – if n is negative.
*
*/
public VeryLongInt (int n)
b. /**
* Returns the number of digits in this VeryLongInt object.
*
* @return the number of digits in this VeryLongInt object.
*
*/
public int size()
c. /**
* Returns true if this VeryLongInt object is less than another VeryLongInt
* object. The worstTime(n) is O(n).
*
* @param otherVeryLong – the other VeryLongInt object.
*
* @return true – if this VeryLongInt is less than otherVeryLong.
*
* @throws NullPointerException – if otherVeryLong is null
*
*/
public boolean less (VeryLongInt otherVeryLong)
d. /**
* Returns true if this VeryLongInt object is greater than another VeryLongInt
* object. The worstTime(n) is O(n).
*
* @param otherVeryLong – the other VeryLongInt object.
*
* @return true – if this VeryLongInt is greater than otherVeryLong.
*
* @throws NullPointerException – if otherVeryLong is null
*
*/
public boolean greater (VeryLongInt otherVeryLong)
e. /**
* Returns true if this VeryLongInt object is equal to a specified object.
* The worstTime(n) is O(n).
*
* @param obj – the specified object that this VeryLongInt is compared to.
*
* @return true – if this VeryLongInt is equal to obj.
*
*/
public boolean equals (Object obj)
f. /**
* Stores a Fibonacci number in this VeryLongInt object.
*
* @param n – the index in the Fibonacci sequence
*
* @throws IllegalArgumentException – if n is not positive
*/
public void fibonacci (int n)
Example Suppose the following message is sent
tempInt.fibonacci (100);
Then tempInt’s value will be 354224848179261915075—the 100th Fibonacci number.
Hint: Mimic the iterative design of the Fibonacci function from Lab 7. Both i and n will be ordinary int variables, but previous, current and temp will be VeryLongInt objects. After the loop, instead of
returning current, the calling object is modified by assigning to digits a copy of current.digits. Get the solution of 6.5
6.6 Assume that myList is (a reference to) an ArrayList<Double> object and that both i and j are int
variables with values in the range from 0 to myList.size() -1, inclusive. Hypothesize what the following accomplishes, and then test your hypothesis.
myList.set (i, myList.set (j, myList.get (i))); Get the solution of 6.6
6.7 Describe how to find the method definitions for the ArrayList class in your computing environment. Get the solution of 6.7
6.8 Modify the simple program in Section 6.2.2 so that all removals are performed in a single loop.
Hint: Create a temporary ArrayList object to hold the un-removed elements. What is a drawback to
this approach? Get the solution of 6.8
6.9 Convert the simple program in Section 6.2.2 into one that uses an array object instead of an ArrayList object. Get the solution of 6.9
6.10 Modify the simple program in Section 6.2.2 to use a binary search instead of the sequential search used in the call to the indexOf method. The Collections class in java.util has a binarySearch method and a sort method. Get the solution of 6.10
6.11 Suppose scoreList is an ArrayList object of Integer elements, and the following message is sent:
scoreList.remove (3);
Does this message remove the element at index 3, or remove the first occurrence of new Integer (3)?
Test your hypothesis. Get the solution of 6.11
6.12 Suppose we create the following ArrayList instance:
ArrayList<String> words = new ArrayList<String>();
And then we insert several words into words. Write the code to print out each element of words that has exactly four letters. You should have three different versions of the code:
a. using an index;
b. using an explicit iterator;
c. using an enhanced for statement. Get the solution of 6.12
6.13 Test and define the following method
/**
* In a given ArrayList, remove all duplicates.
* The worstTime(n) is O(n2 ).
*
* @param list - the given ArrayList.
*
* @return – An ArrayList that is identical to list except only the first
* occurrence of duplicate elements remains.
*
* @throws NullPointerException - if list is null.
*
*/
public static <T> ArrayList <T> uniquefy (ArrayList <T> list)
For example, suppose myList consists of references to Integer objects with the following values, in
sequence 3, 8, 6, 4, 8, 7, 8, 9, 4
Then the ArrayList returned by the call to uniquefy (myList) will consist of references to Integer
objects with the following values, in sequence
3, 8, 6, 4, 7, 9 Get the solution of 6.13
