SETS AND MAPS - Introduction to Java Programming: Comprehensive Version - page 808

57 }
58
59

public static long getRemoveTime(Collection<Integer> c) {

60 long startTime = System.currentTimeMillis();

61
62

for ( int i = 0 ; i < N; i++)

63 c.remove(i);

remove from container

64
65 return System.currentTimeMillis() - startTime; return execution time

66 }
67 }

Member test time for hash set is 20 milliseconds
Remove element time for hash set is 27 milliseconds
Member test time for linked hash set is 27 milliseconds
Remove element time for linked hash set is 26 milliseconds
Member test time for tree set is 47 milliseconds
Remove element time for tree set is 34 milliseconds
Member test time for array list is 39802 milliseconds
Remove element time for array list is 16196 milliseconds
Member test time for linked list is 52197 milliseconds
Remove element time for linked list is 14870 milliseconds

=

The program creates a list for numbers from 0 to N-1 (for N 50000 ) (lines 8-10) and shuf-

fles the list (line 11). From this list, the program creates a hash set (line 14), a linked hash set
(line 21), a tree set (line 28), an array list (line 35), and a linked list (line 42). The program
obtains the execution time for testing whether a number is in the hash set (line 16), linked hash
set (line 23), tree set (line 30), array list (line 37), and linked list (line 44), and obtains the
execution time for removing the elements from the hash set (line 18), linked hash set (line 25),
tree set (line 32), array list (line 39), and linked list (line 46).
The getTestTime method invokes the contains method to test whether a number is
in the container (line 54) and the getRemoveTime method invokes the remove method to
remove an element from the container (line 63).
As these runtimes illustrate, sets are much more efficient than lists for testing whether
an element is in a set or a list. Therefore, the No-Fly list should be implemented using a set
instead of a list, because it is much faster to test whether an element is in a set than in a list.
You may wonder why sets are more efficient than lists. The questions will be answered in
Chapters 24 and 27 when we introduce the implementations of lists and sets.

sets are better

21.10 Suppose you need to write a program that stores unordered non-duplicate elements,
what data structure should you use?
21.11 Suppose you need to write a program that stores non-duplicate elements in the order
of insertion, what data structure should you use?
21.12 Suppose you need to write a program that stores non-duplicate elements in increasing
order of the element values, what data structure should you use?
21.13 Suppose you need to write a program that stores a fixed number of the elements (pos-
sibly duplicates), what data structure should you use?

✓ ✓

Check

Point

21.14

Suppose you need to write a program that stores the elements in a list with frequent opera-
tions to add and insert elements at the end of the list, what data structure should you use?

21.15

Suppose you need to write a program that stores the elements in a list with frequent
operations to add and insert elements at the beginning of the list, what data structure
should you use?