List processing

List processing is the name for a number of techniques to help manipulate collections of data. Although arrays, structures, and unions are also used for manipulating collections of data, list processing techniques are more flexible because they allow collections of data to be indefinitely reordered and extended during program execution.

The purpose here is not to illustrate these techniques but is to show how based variables and locator variables serve as a basis for this type of processing.

In list processing, a number of based variables with many generations can be included in a list. Members of the list are linked together by one or more pointers in one member identifying the location of other members or lists. The allocation of a based variable cannot specify where in main storage the variable is to be allocated (except that you can specify the area in which you want it allocated). In practice, a chain of items can be scattered throughout main storage, but by accessing each pointer the next member is found. A member of a list is usually a structure or union that includes a pointer variable. The following example creates a list of structures:

  dcl 1 STR based(H),
        2 P pointer,
        2 data,
      T  pointer;

        allocate STR;
        T=H;

        do loop;
          allocate STR set(T->P);
            T=T->P;
            T->P=null;
            .
            .
            .
       end;

The structures are generations of STR and are linked by the pointer variable P in each generation. The pointer variable T identifies the previous generation during the creation of the list. The first ALLOCATE statement sets the pointer H to identify it. The pointer H identifies the start, or head, of the list. The second ALLOCATE statement sets the pointer P in the previous generation to identify the location of this new generation. The assignment statement T=T->P; updates pointer T to identify the location of the new generation. The assignment statement T->P=NULL; sets the pointer in the last generation to NULL, giving a positive indication of the end of the list.

Figure 1 shows a diagrammatic representation of a one-directional chain.

Figure 1. Example of one-directional chain

Unless the value of P in each generation is assigned to a separate pointer variable for each generation, the generations of STR can be accessed only in the order in which the list was created. For the above example, the following statements can be used to access each generation in turn:

  do T=H
    repeat(T->P)
    while (T¬=null);
      .
      .
      .
      T->data;
      .
      .
      .
end;

The foregoing examples show a simple list processing technique, the creation of a unidirectional list. More complex lists can be formed by adding other pointer variables into the structure or union. If a second pointer is added, it can be made to point to the previous generation. The list is then bidirectional; from any item in the list, the previous and next items can be accessed by using the appropriate pointer value. Instead of setting the last pointer value to the value of NULL, it can be set to point to the first item in the list, creating a ring or circular list.

A list need not consist only of generations of a single based variable. Generations of different based structure or unions can be included in a list by setting the appropriate pointer values. Items can be added and deleted from a list by manipulating the values of pointers. A list can be restructured by manipulating the pointers so that the processing of data in the list can be simplified.