Java Reference
In-Depth Information
Display 15.38
Set Class Demo
(part 2 of 2)
39 System.out.print("Intersection of green and round: ");
40 round.intersection(green).output( );
41 }
42 }
Sample Dialogue
Contents of set round:
grapes pie ball peas
Contents of set green:
Grass garden hose grapes peas
ball in set round? true
ball in set green? false
ball and peas in same set? true
pie and grass in same set? false
Union of green and round: garden hose grass peas ball pie grapes
Intersection of green and round: peas grapes
Efficiency of Sets Using Linked Lists
We can analyze the efficiency of our set data structure in terms of the fundamental set
operations. Adding an item to the set always inserts a new node on the front of the
list. This requires constant, or
O
(
1
), steps. The
contains
method iterates through
the entire set looking for the target, which requires
O
(
n
) steps. When we invoke the
union
method for sets
A
and
B
, it iterates through both sets and adds each item into a
new set. If there are
n
items in set
A
and
m
items in set
B
, then
n
+
m
add methods are
invoked. However, there is a hidden cost because the
add
method searches through its
entire list for any duplicates before a new item is added. Although beyond the scope
of this text, the additional cost results in
O
(
m
n
)2 steps. Finally, the
intersection
method applied to sets
A
and
B
invokes the
contains
method of set
B
for each item in
set
A
. Because the
contains
method requires
O
(
m
) steps for each item in set
A
, then
this requires
O
(
m
)
+
*
O
(
n
) steps, or
O
(
mn
) steps. These are inefficient methods in our
implementation of sets. A different approach to represent the set—for example, one
that used hash tables instead of a linked list—could result in an
intersection
method
that runs in
O
(
n
m
) steps. Nevertheless, our linked list implementation would
probably be fine for an application that uses small sets or for an application that does
not frequently invoke the
intersection
method, and we have the benefit of relatively
simple code that is easy to understand.
If we really need the efficiency, then we could maintain the same interface to the
Set<T>
class but replace our linked list implementation with something else. If we
used the hash table implementation from Section 15.5, then the
contains
method
+
