3.6.3 Lists Stored in Languages without Records

In some languages, such as FORTRAN, there is no dynamic memory, nor are there pointer variables or records. In such a language, the records themselves must be implemented by the programmer. They may be stored in single or multiple arrays, as discussed in Chapter 2. Since the list records now have an additional link field indicating their successor, they need not be stored sequentially and may be located anywhere in the array or multiarrays, as long as they do not overlap. An additional variable is needed for the head of the list. Once these arrays are set up, the programmer may write functions to access each field of a record and functions to copy one record's value into another record, or to copy a record's field value into another record's field. These might include

next(pointer)

Returns a copy of the link field value of the record pointed to by pointer.

setlink(pointer1,pointer2)

Sets the value of the link field of the record pointed to by pointer1 to pointer2.

setlinfo(pointer1,pointer2)

Sets the value of the information field of the record pointed to by pointer1 to the value of the information field of the record pointed to by pointer2.

In FORTRAN, the array or multiarray in which the records are kept could be declared to be stored in the FORTRAN common area or else must be passed as parameters to these functions. Once they are written, for all intents and purposes the language has records. These records can be accessed, copied, or modified by using these functions. Although the programmer must do all this work initially, from this point on the situation is conceptually the same as in Section 3.6.2. That is, the actual implementation of the records may be forgotten; they are treated as if stored in an array of records, just as in C. The problem of writing an avail function still remains, and it is addressed in the next section.

In FORTRAN, although storage for records kept in lists must be managed, the programmer does not need to manage storage for individual elements or for arrays of elements. To refer in a program to an element n, or an array data, simply declare n to be an element, and data to be an array. Then use the operations available in FORTRAN to enter specific values into n or data. This works because individual elements and arrays are data structures directly available in FORTRAN. Lists, on the other hand, are not directly available and must be built up explicitly by storing their records in arrays. Consequently, the programmer must determine where storage is available to create a record when the need arises.

In C it is not necessary to implement records of lists explicitly in arrays. Instead, dynamic data structures may be used. A data structure is dynamic if it is built during execution of a program and storage is allocated for its components at that time. Dynamic data structures are built simply by asking for storage to be allocated for a record in dynamic memory. A pointer will then be assigned to point to that storage. Using the pointer, appropriate values may be assigned to the fields of the new record. These fields may be referred to directly, using naming conventions in the language. Special functions to store or access information from the fields of the record need not be written.

Records still need to be inserted properly in a dynamic data structure. Commands directly available in the language may be used to create or reclaim records, or reclamation may be left to the implicit storage reclamation provided by the language. Thus the definition, creation, reclamation, and manipulation of dynamic data structures become easier.