Java Reference
In-Depth Information
variable contains a reference 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 virtually 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"
. Because the linked list is storing a reference to each object in the
set, it is possible to place an item in multiple sets by referencing it from multiple linked
lists. In Display 15.36 ,
"peas"
is in both sets because 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.
Display 15.36
Sets Using Linked Lists
null
round
grass
peas
ball
pie
green
null