The linear search problem in computing

This thesis was scanned from the print manuscript for digital preservation and is copyright the author.

A linked list is a form of data structure which must be searched sequentially. A search of a linked list begins at the first record in the list, which contains a pointer to the location of the second element, and so on (see figure 1). This arrangement may be likened to a series of books on a shelf, indistinguishable until removed and examined. In order to find a particular book, it would be necessary to systematically remove and examine each book from the left hand edge of the shelf, for instance.