As presented in the textbook, linked-lists must be searched sequentially. For large lists, this can result in poor performance. A common technique for improving list-searching performance is to create and maintain an index to the list. An index is a set of references to key places in the list.
For example, an application that searches a large list of names could improve performance by creating an index with 26 entries-one for each letter of the alphabet. A search operation for a last name beginning with ‘Y' would then first search the index to determine where the ‘Y' entries began, then go to the list at that point and search linearly until the desired name was found.
This would be much faster than searching the linked list from the beginning. Use the List class of Figure 21.3 in the textbook as the basis for an IndexedList class that implements the approach described above. Write a program that demonstrates the operation of your IndexedList class.