How are the nodes in a generalized list connected with each other?
1. Analysis of node relations in the head–tail representation method of generalized list
i. Analysis of node relations in the head–tail decomposition method of generalized list
According to the definition of generalized list, if the generalized list is not empty, then we can decompose it into list head and list tail; in the opposite direction, a pair of defined head and tail can uniquely define a generalized list: Generalized list = head + tail.
We can recursively use the head–tail representation method of generalized list, in order to decompose generalized lists into atoms eventually.
For example: E = (a, (b, c, d)). Recursively decomposing it with head–tail representation method, we obtain:
– Head(E) = a Tail(E) = E1(b,c,d)
– Head(E1) = b Tail(E1) = E2(c,d)
– Head(E2) = c Tail(E2) = E3(d)
The corresponding diagram of decomposition is shown in →Fig. 1.97.
Decomposition diagram for the head–tail representation method of generalized list.
ii. Analysis on the relations between nodes in the sublist
The analysis on sublist is done by decomposing a nonempty generalized list into n juxtaposed sublists, until they are decomposed into atoms:
Generalized list = Sublist 1 + Sublist 2 + … + Sublist n
→Figure 1.98 gives the decomposition diagram of generalized list E = (a, (b, c, d)) and L = (a, (x, y), ((z))).
The decomposition diagram of sublist analysis method of generalized list.
From the decomposition diagram, we can see that the two decomposition methods for head–tail representation method arrive at the same result eventually.
2. Analysis on the connections between nodes in graphical representation method of generalized list
We can first analyze the two simple forms: linear list and pure list, since the corresponding graphs for these two forms are the general forms of a tree. We can directly use the storage plan for tree, and then test whether the storage of reentrant list and recursive list can be realized using the same plan.
To store a generic tree with homogeneous structure, we need to deal with the degree of the tree, which determines the number of pointer fields in the list node. Therefore, it is not a commonly applicable method. If we convert the generic tree into a binary tree for storage, then the storage of its linked list will be done with binary linked list, which is a common solution.
From the description of the storage relations of trees and binary trees in Section 5.2.4, we know that the storage structures of a tree constructed with child–sibling representational method and that constructed as the binary linked list for the corresponding binary tree are completely the same. In the linked storage of generalized list, we usually call this storage method “child–sibling representation method,” as shown in →Fig. 1.99 for a concrete example.
Child–sibling representational method of generalized list.
When we compare two storage structures, they have their respective features. For the first storage structure, except for the head pointer of the empty list, which is empty, for any nonempty list, its head pointer points to one list node. From this kind of storage structure, it is easy to distinguish the level of the atom and sublist; the number of list nodes at the highest level is the length of the generalized list. Therefore, certain operations on the generalized list become relatively convenient, for example, obtaining the length and depth of the generalized list and obtaining the head and tail of the list. However, its shortcomings are also obvious: there are a lot of list nodes in the storage structures; they occupy a lot of storage space, and they do not correspond to the number of pairs of brackets in the generalized list.
The features of the second storage structure are exactly the reverse: the number of sublist nodes is low and the same as the number of pairs of brackets in the generalized list. However, it is inconvenient to write recursive algorithms on this structure.