Inserting or deleting a record from a list-structure is done using the same procedures as in Chapter 3. Determining where to insert or delete involves a traversal through the records to locate the desired position. Unlike the chain, for which there is a natural order in which to traverse the records, list-structures have no simple natural order. Instead, the order in which records are to be accessed and processed is defined as follows:
To traverse a list-structure,
Access each record on the main list in order and
1. Process the record
2. If the record is complex, then traverse the complex record's sublist.
Notice that the definition is actually recursive, since a complex record's sublist is itself a list-structure. To see how to apply it, consider formula in Figure 6.4. The records are numbered for ease of reference.
To determine the order in which records are accessed and processed in a traversal of the list-structure formula, apply the definition. It specifies that records 1 and 2 on the main list be accessed and processed in sequence. Since record 2 is complex, sublist 1 must be traversed. At the finish of traversal of sublist 1, it will be necessary to continue where processing left off on the main list. To know where to resume, save P1. To traverse sublist 1, apply the definition to it, and access and process records 3 and 4 in order. Since record 4 is complex, traverse sublist 2. Save P3 to know where to resume when its traversal is complete.
To traverse sublist 2, apply the definition of traversal to it, and so access and process records 5 and 6. Since the link field of record 6 is null, no records remain on this sublist, so its traversal is complete.
Which task should be done now? Step 2 of the traversal definition has just been applied to sublist 2. The next record of some sublist must now be accessed. What record? It is the successor record of the complex record梤ecord 4梬hose sublist traversal was just completed. P3, which was saved for just this moment, points to record 7, so let the program follow it. Since P3 is no longer needed, discard it. Since record 7 is complex, traverse sublist 3. Continuing in this way, the program would access and process the records in the order in which they are numbered.
From this example it can be seen that whenever the link field of the record just accessed and processed is null, the traversal of some sublist has been completed and the program must determine where to go next. Each time the processing of a complex record was finished, the content of its link field was saved before traversing its sublist. In formula, this leads to saving P1, then P3. After record 6 comes a null link field signifying the completion of the traversal of sublist 2. P3 then tells the program where to go next. Once followed, it can be forgotten. Pl is still remembered, and P5, P7, and P9 need to be remembered in turn. After dealing with record 14, the program encounters its null link value, which signifies completion of sublist 4's traversal. Where does it go? It follows P9 and needs to remember only P7, P5, and P1, and so on.