Java Reference
In-Depth Information
L4
L1
L3
L2
B
C
D
A
Figure12.3 Example of a cyclic list. The shape of the structure is a directed
graph.
that label will be substituted when we write out the list. Thus, the bracket notation
for the list of Figure 12.2 could be written
hhL1 :ha; bii;hL1; L2 : ci;hL2; d; L3 : ei;hL3ii:
A cyclic list is a list structure whose graph corresponds to any directed graph,
possibly containing cycles. Figure 12.3 illustrates such a list. Labels are required to
write this in bracket notation. Here is the bracket notation for the list of Figure 12.3.
hL1 :hL2 :ha; L1ii;hL2; L3 : bi;hL3; c; di; L4 :hL4ii:
Multilists can be implemented in a number of ways. Most of these should be
familiar from implementations suggested earlier in the topic for list, tree, and graph
data structures.
One simple approach is to use a simple array to represent the list. This works
well for chains with fixed-length elements, equivalent to the simple array-based list
of Chapter 4. We can view nested sublists as variable-length elements. To use this
approach, we require some indication of the beginning and end of each sublist. In
essence, we are using a sequential tree implementation as discussed in Section 6.5.
This should be no surprise, because the pure list is equivalent to a general tree
structure. Unfortunately, as with any sequential representation, access to the nth
sublist must be done sequentially from the beginning of the list.
Because pure lists are equivalent to trees, we can also use linked allocation
methods to support direct access to the list of children. Simple linear lists are
represented by linked lists. Pure lists can be represented as linked lists with an
additional tag field to indicate whether the node is an atom or a sublist. If it is a
sublist, the data field points to the first element on the sublist. This is illustrated by
Figure 12.4.
Another approach is to represent all list elements with link nodes storing two
pointer fields, except for atoms. Atoms just contain data. This is the system used by
the programming language LISP. Figure 12.5 illustrates this representation. Either
the pointer contains a tag bit to identify what it points to, or the object being pointed
to stores a tag bit to identify itself. Tags distinguish atoms from list nodes. This
Search WWH ::




Custom Search