We now present a case study to illustrate the versatility of lists intertwined with pointers. When the name of a record or a pointer to it is known, retrieval of the record is simple. It may be directly accessed and processed to suit our needs. Slightly more difficult is the retrieval of a record that can be recognized when encountered but whose location is unknown. In order to retrieve it the records must be traversed until the desired one is encountered.
When large collections of records are involved, traversing all the records to find one is not feasible. The problem is not so much that retrieving one desired record takes too long but that many retrievals in rapid succession cause too much delay for the later retrievals. Imagine 1,000 computer terminals linked to a central computer. The banking terminals known as automatic tellers are an example. Suppose 200 requests occur in rapid succession for the retrieval of records. If 1 million records need to be traversed, the retrieval of an individual record could easily take a second, so the last of the 200 requests to be processed would be honored only after more than 3 minutes of elapsed time. No one wants to wait at a terminal for 3 minutes before each request is answered. In the meantime, even more requests become backlogged.
The basic technique to avoid traversing all stored records is to focus the search on a smaller group of records known to contain the desired one. This is the essence of most faster retrieval algorithms. In this case study, lists will be used to organize the data so that the search may be localized in this way. In Chapters 8 and 9 the search problem is presented in a more general context for information stored in random access internal memory, and in Chapter 10 for information stored in external memory.
6.5.5 Retrieving Information from the System