The collections api - Data Structures and Problem Solving Using Java - page 289

The RandomAccess interface contains no methods but is intended to serve
as a marker: a List class implements the interface only if its get and
set methods are very efficient. Accordingly, ArrayList implements the
RandomAccess interface. Implement static method removeEveryOtherItem ,
described in Exercise 6.17. If list implements RandomAccess (use an
instanceof test), then use get and set to reposition items at the front half
of the list. Otherwise, use an iterator that is efficient for linked lists.

6.20

Write, in as few lines as possible, code that removes all entries in a
Map whose values are null .

6.21

The listIterator method set allows the caller to change the value of
the last item that was seen. Implement the toUpper method (that
makes the entire list upper case) shown below using a listIterator :

6.22

public static void toUpper( List<String> theList )

Method changeList replaces each String in the list by both its lower
case and upper case equivalents. Thus if the original list contained
[ Hello , NewYork ], then new list will contain [ hello , HELLO , newyork , NEWYORK ].
Use the listIterator add and remove methods to write an efficient
implementation for linked lists of method changeList :

6.23

public static void changeList( LinkedList<String> theList )

PROGRAMMING PROJECTS
6.24

A queue can be implemented by using an array and maintaining the
current size. The queue elements are stored in consecutive array posi-
tions, with the front item always in position 0. Note that this is not the
most efficient method. Do the following:
a. Describe the algorithms for getFront , enqueue , and dequeue .

b. What is the Big-Oh running time for each of getFront , enqueue ,

and dequeue using these algorithms?

c. Write an implementation that uses these algorithms using the pro-

tocol in Figure 6.28.

The operations that are supported by the SortedSet can also be imple-
mented by using an array and maintaining the current size. The array
elements are stored in sorted order in consecutive array positions. Thus
contains can be implemented by a binary search. Do the following:
a.

6.25

Describe the algorithms for add and remove .

b. What is the running time for these algorithms?