Java Collections Framework - Building Java Programs: A Back to Basics Approach - page 708

Self-Check Problems
Section 11.1: Lists
1. When should you use a LinkedList instead of an ArrayList ?
2. Would a LinkedList or an ArrayList perform better when run on the following code? Why?
public static int min(List<Integer> list) {
int min = list.get(0);
for (int i = 1; i < list.size(); i++) {
if (list.get(i) < min) {
min = list.get(i);
}
}
return min;
}
3. What is an iterator? Why are iterators often used with linked lists?
4. Write a piece of code that counts the number of duplicate elements in a linked list, that is, the number of elements
whose values are repeated at an earlier index in the list. Assume that all duplicates in the list occur consecutively. For
example, the list (1, 1, 3, 5, 5, 5, 5, 7, 7, 11) contains five duplicates: one duplicate of element value 1 ,
three duplicates of element value 5 , and one duplicate of element value 7 .
5. Write a piece of code that inserts a String into an ordered linked list of String s, maintaining sorted order.
For example, for the list ("Alpha", "Baker", "Foxtrot", "Tango", "Whiskey") , inserting "Charlie" in
order would produce the list ("Alpha", "Baker", "Charlie", "Foxtrot", "Tango", "Whiskey") .
6. Write a method called removeAll that accepts a linked list of integers as a parameter and removes all occurrences
of a particular value. You must preserve the original relative order of the remaining elements of the list. For example,
the call removeAll(list, 3) would change the list (3, 9, 4, 2, 3, 8, 17, 4, 3, 18, 2, 3) to (9, 4,
2, 8, 17, 4, 18, 2) .
7. Write a method called wrapHalf that accepts a linked list of integers as a parameter and moves the first half of the
list to the back of the list. If the list contains an odd number of elements, the smaller half is wrapped (in other words,
for a list of size N, the middle element, N/2, becomes the first element in all cases). For example, calling wrapHalf
on the list (1, 2, 3, 4, 5, 6) , would change that list into (4, 5, 6, 1, 2, 3) . For the list (5, 6, 7, 8,
9) , the result would be (7, 8, 9, 5, 6) .
8. What is an abstract data type (ADT)? What ADT does a linked list implement?
9. Self-Check Problem 4 asked you to write code that would count the duplicates in a linked list. Rewrite your code as
a method called countDuplicates that will allow either an ArrayList or a LinkedList to be passed as the
parameter.
Section 11.2: Sets
10. A List has every method that a Set has, and more. So why would you use a Set rather than a List ?
11. When should you use a TreeSet , and when should you use a HashSet ?