6.1.1 A Definition of List-structures

Each of the example lists organizes information by collecting related data on sublists. They are a step up in complexity from the chains of Chapter 3 but do not illustrate the most complex lists, which allow sharing of records and sublists. Sharing means that more than one record can point to another record or sublist. Records can also have additional pointer fields linking records to form intertwined lists. However, this chapter concentrates primarily on list-structures. They may be defined formally by either of two equivalent definitions:

A list-structure is a collection of simple and complex records linked by pointers in the following way.

The link and sublist fields of each record contain pointers to records of the collection.

Each record of the collection has no more than one pointer to it from any record of the collection.

Or recursively:

A list-structure is a list of simple and complex records whose complex record's sublist fields point to distinct list-structures called sublists. The predecessor of each record must be unique.

The first definition treats list-structures as a collection of linked records but does not convey their inherent structure. The recursive definition emphasizes this structure, making clear how a list-structure is itself built from other list-structures.

It is evident that each list of Figure 6.1 satisfies the first definition. To see that they also satisfy the recursive definition, consider the accounts list. The main list consists of a list of simple and complex records, so it is necessary to check that the complex record's sublists are themselves list-structures. The first main-list record's sublist is a list-structure since the sublist's main list satisfies the definition and its complex record points to a list-structure, a single list record. The second main-list record's sublist is itself a list whose complex record's sublist is a list-structure, the null list-structure.

(a) List with Shared Sublists

(b) List with a Loop

Figure 6.3 Two Lists That Are Not List-structures

The lists sam and sally in Figure 6.3 are not list-structures, since they fail to satisfy the definitions. Sam has shared sublists; sally has a loop.