Youcanforgetaboutusing BitSet (assumingthateachentryoccupiesasinglebit)
because10,000,000,000istoolargetopasstothe BitSet(int nbits) construct-
java.lang.OutOfMemoryError at runtime.
entries are nonzero at any one time. After all, a sparse matrix has a sparse number of
nonzero entries. This is a lot more manageable.
Youwon'tuse BitSet torepresentthismatrixbecauseyou'llassumethateachmat-
rix entry is an object. You can't use a two-dimensional array to store these objects be-
cause the array would need 100,000 rows by 100,000 columns to properly index the
sparse matrix, and you would exhaust memory by being extremely wasteful in storing
zero (or null, in the case of object) values.
There is another way to represent this matrix, and that is to create a linked list of
A node is an object consisting of value and link fields. Unlike an array, where each
can store multiple values of different types. It can also store links (references to other
Listing 5-28. A node consists of value fields and link fields
// value field
// link field
Node describessimplenodeswhereeachnodeconsistsofasingle name valuefield
andasingle next linkfield.Noticethat next isofthesametypeastheclassinwhich
it is declared. This arrangement lets a node instance store a reference to another node
instance (which is the next node) in this field. The resulting nodes are linked together.
Listing 5-29 presents a Nodes class that demonstrates connecting Node s together
intoa linked list ,andtheniteratingoverthislisttooutputthevaluesofthe name fields.