Java Reference
In-Depth Information
15.6
Sets
There are two classes in good society in England. The equestrian classes
and the neurotic classes.
GEORGE BERNARD SHAW,
Heartbreak House
A set is a collection of elements in which order and multiplicity are ignored. Many prob-
lems in computer science can be solved with the aid of a set data structure. A variation
on linked lists is a straightforward way to implement a set. In this implementation the
items in each set are stored using a singly linked list. The
data
variable contains a refer-
ence to an object we wish to store in the set, whereas the
link
variable refers to the next
Node<T>
in the list (which in turn contains a reference to the next object to store in the
set). The node class for a generic set of objects can begin as follows:
private
class
Node<T>
{
private
T data;
private
Node<T> link;
...
A complete listing is provided in Display 15.37. The
Node
class is a private inner
class, similar to how we constructed the generic
LinkedList3<T>
class in Display 15.8.
In fact, the set operations of
add
,
contains
,
output
,
clear
,
size
, and
isEmpty
are vir-
tually identical to those from Display 15.8. The
add
method (which was
addToStart
)
has been slightly changed to prevent duplicate items from being added into the set.
Display 15.36 illustrates two sample sets stored using this data structure. The set
round
contains
"peas"
,
"ball"
, and
"pie"
, whereas the set
green
contains
"peas"
and
"grass"
. Since the linked list is storing a reference to each object in the set, it is possi-
ble to place an item in multiple sets by referencing it from multiple linked lists. In Dis-
play 15.36,
"peas"
is in both sets since it is round and green.
Fundamental Set Operations
The fundamental operations that our set class should support are as follows:
• Add Element. Add a new item into a set.
• Contains. Determine if a target item is a member of the set.
• Union. Return a set that is the union of two sets.
• Intersection. Return a set that is the intersection of two sets.
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. Other useful set operations include
methods to retrieve the cardinality of the set and to remove items from the set.
