Reading: Wood, Chapter 2, Sections 2.2.1, 2.3.2

Wood, Chapter 8, Sections 8.3.3, 8.3.4

Wood, Chapter 10, Sections 10.3

1. As discussed in the lecture notes, the worst-case time performance of a basic sequential search through an unordered list of elements is O(n) since every element of the list must be examined to see if it matches. However, the expected-case performance can be improved if more frequently accessed items are kept at the front of the list (assuming a non-uniform probability distribution of item lookups). In this case, the amortized case performance will also improve.

One way to achieve improved performance is using a move-to-front sequential search. In this search technique, an item is found by sequentially searching for the item from the front of the list as in an exhaustive search. However, if the item is found, the item is moved to the front of the list in the hope that subsequent searches for the item will find the item earlier on in the list than before. For simplicity, we will only move the first occurrence of the item; all other occurrences of the item in the list are left unmoved.

  1. Write a private method called moveToFront(w) for both the block and linked representations of the list ADT that moves the item under the window location w to the front of the list. The method should move the item to the front, leaving the window over the subsequent item.

  2. What is the time performance for this method for each representation of the list ADT?

  3. Are there any advantages of "directly" coding these methods versus making use of existing list ADT methods?

  4. Use the moveToFront(w) method to write a method called mtfSearch(Object o) that implements a move-to-front search for o in the list.