7.3.1 An Unordered List

An unordered list would enter each name sequentially as it is declared. The lookup operation must then search linearly, and, thus, in the worst case, would have to look at all n entires and in the average case at half of them. Thus the search time is of order n, O(n).

There is really no good reason to have such an inefficient data structure unless it is known that the number of entries will be exceedingly small, perhaps less than a couple dozen names.

Example 2 shows an unordered list structure for the program of Example 1

Example 2 An unordered list structure

       Characters   Class     Scope        Other Attributes
                                       Declared  Referenced   Other

        Main        Program    0        Line 1
          a         Variable   0        Line 2     Line 11
          b         Variable   0        Line 2     Line 7
          P         Procedure  0        Line 3     Line 11   1 param, x
          x         Parameter  1        Line 3     
          a         Variable   1        Line 4     Line 6