Collecting Objects - Beginning Java 7 - page 530

Youcanforgetaboutusing BitSet (assumingthateachentryoccupiesasinglebit)
because10,000,000,000istoolargetopasstothe BitSet(int nbits) construct-
or;someinformationwillbelostwhenyoucastthislongintegertoaninteger.Youcan
alsoforgetaboutusinganarraybecauseyou'llexhausttheJVM'smemoryandobtaina
java.lang.OutOfMemoryError at runtime.
Becauseyou'redealingwithasparsematrix,assumethatnomorethan25,000table
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
nodes.
A node is an object consisting of value and link fields. Unlike an array, where each
elementstoresasinglevalueofthesameprimitivetypeorreferencesupertype,anode
can store multiple values of different types. It can also store links (references to other
nodes).
Consider Listing 5-28 ' s Node class:
Listing 5-28. A node consists of value fields and link fields
class Node
{
// value field
String name;
// link field
Node next;
}
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.