Self-optimizing Lists

When doing a linear search in an unsorted list of length N, the worst case run time is proportional to N, but the time it takes to find an item depends on where that item is in the list. Items near the front of the list are found quickly, while items near the end of the list are only found after close to N steps. If the same list is going to be searched many times, it would make sense to put the items that are most likely to be searched for near the front of the list, so that they can be found quickly. However, you don't necessarily know in advance which items are likely to be searched for; you have to wait and see which ones are most likely in practice. This leads to the idea of a self-optimizing list.

In a self-optimizing list, every time an item is searched for and found, that item is moved closer to the front of the list, on the theory that over time, this will keep items that are more likely to be searched for near the front of the list. There are at least two versions of this idea. In one version, when an item is found it is moved to the front of the list (unless it s already there). In the second version, when an item is found, it is swapped with the item that precedes it in the list (unless it s at the front of the list).

You will write a program that empirically tests both ideas. To run an empirical test, you should place the integers I to 100 into a list in random order. Do a large number of searches (say, one million). You should pick the numbers to be searched for using some method such that numbers have different probabilities of being picked. (Exactly how you choose the numbers is up to you, but the probabilities will have to be significantly different for you to see any effect.) Keep track of the total number of comparisons done during all of the searches. Then at the end, you can find the average number of comparisons per search.

You should perform such an empirical test for each of the two versions of self-optimizing lists, and print out the average number of comparisons per search in each case. (If you like, you could also run the test for a static list, where you don't modify the list after doing a search.) The goal is to see how well the self-optimizing list idea works, and which version gives better results.

For the lists in this program, you are required to use your own implementation of doubly linked lists. Do not use built-in Java data types such as ArrayList or LinkedList., You can use the following class for the nodes in a doubly linked list:

static class ListNode

{
int item; // The list item stored in this node.
ListNode prey; // Pointer to previous node (or null for first node).
ListNode next; // Pointer to next node (or null for last node).

}

You can add methods and/or constructors to this class, if you need them for your program.