Java Reference
In-Depth Information
We should also make an iterator so that every element can be retrieved from a set.
This is left as a programming project for the reader (Programming Project 15.7).
Other useful set operations include methods to retrieve the cardinality of the set and to
remove items from the set.
Code to implement sets is provided in Display 15.37. The
add
method is similar to
adding a node to the front of a linked list. The
head
variable always references the first
node in the list. The
contains
method is identical to the
find
method for a singly
linked list. We simply loop through every item in the list looking for the target.
The
union
method combines the elements in the calling object's set with the
elements from the set of the input argument,
otherSet
. To union these sets, we first
create a new empty
Set<T>
object. Next, we iterate through both the calling object's
set and
otherSet
's set. All elements are added (which creates new references to the
items in the set) to the new set. The
add
method enforces uniqueness, so we do not
have to check for duplicate elements in the
union
method.
The
intersection
method is similar to the
union
method in that it also creates
a new empty
Set<T>
object. In this case, we populate the set with items that are
common to both the calling object's set and
otherSet
's set. This is accomplished by
iterating through every item in the calling object's set. For each item, we invoke the
contains
method for
otherSet
. If
contains
returns
true
, then the item is in both
sets and can be added to the new set.
A short demonstration program is shown in Display 15.38.
Display 15.37
Set<T>
Class
(part 1 of 3)
1
// Uses a linked list as the internal data structure
2
// to store items in a set.
3
public class
Set<T>
4 {
5
private class
Node<T>
6 {
7
private
T data;
8
private
Node<T> link;
9
public
Node( )
10 {
11
data =
null
;
12
link =
null
;
13 }
14
public
Node(T newData, Node<T> linkValue)
15 {
16
data = newData;
17
link = linkValue;
18 }
19 }
//End of Node<T> inner class
(continued)