Java Reference
In-Depth Information
Display 15.38
Set Class Demo
(part 2 of 2)
27
System.out.println("ball and peas in same set? " +
28
((round.contains("ball") &&
29
(round.contains("peas"))) ||
30
(green.contains("ball") &&
31
(green.contains("peas")))));
32
System.out.println("pie and grass in same set? " +
33
((round.contains("pie") &&
34
(round.contains("grass"))) ||
35
(green.contains("pie") &&
36
(green.contains("grass")))));
37
System.out.print("Union of green and round: ");
38
round.union(green).output( );
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
+