Java Reference
In-Depth Information
X1
X4
Y1
Y3
Z1
Z2
A1
A2
Figure12.1
Example of a multilist represented by a tree.
L2
L1
E
L3
C
D
A
B
Figure12.2
Example of a reentrant multilist. The shape of the structure is a
DAG (all edges point downward).
In this example, the list has four elements. The second element is the sublist
hy1;ha1; a2i; y3i and the third is the sublist hz1; z2i. The sublist hy1;ha1; a2i; y3i
itself contains a sublist. If a list L has one or more sublists, we call L a multi-
list. Lists with no sublists are often referred to as linear lists or chains. Note that
this definition for multilist fits well with our definition of sets from Definition 2.1,
where a set's members can be either primitive elements or sets.
We can restrict the sublists of a multilist in various ways, depending on whether
the multilist should have the form of a tree, a DAG, or a generic graph. A pure list
is a list structure whose graph corresponds to a tree, such as in Figure 12.1. In other
words, there is exactly one path from the root to any node, which is equivalent to
saying that no object may appear more than once in the list. In the pure list, each
pair of angle brackets corresponds to an internal node of the tree. The members of
the list correspond to the children for the node. Atoms on the list correspond to leaf
nodes.
A reentrant list is a list structure whose graph corresponds to a DAG. Nodes
might be accessible from the root by more than one path, which is equivalent to
saying that objects (including sublists) may appear multiple times in the list as long
as no cycles are formed. All edges point downward, from the node representing a
list or sublist to its elements. Figure 12.2 illustrates a reentrant list. To write out
this list in bracket notation, we can duplicate nodes as necessary. Thus, the bracket
notation for the list of Figure 12.2 could be written
hhha; bii;hha; bi; ci;hc; d; ei;heii:
For convenience, we will adopt a convention of allowing sublists and atoms to be
labeled, such as “L1:”. Whenever a label is repeated, the element corresponding to
