7.3.2 An Ordered List

By ordered, we mean ordered according to the characters in the name.

With an ordered array, a binary search could be done in O(log₂n) time on the average, but the enter operation will take more time since elements may have to be moved. To do a binary search, however, we need to implement the ordered list as an array.

Representing the list as an ordered linked list brings us back to O(n) for the lookup operation although the enter operation would, on the average, be simpler since only pointers need to be changed rather than changing the position of each element.

Example 3 shows an ordered list. Notice that we cannot see whether this has been implemented as an array or as a linked list.

Example 3 An ordered list structure

       Characters   Class     Scope        Other Attributes
                                       Declared  Referenced   Other

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