CSC148 - Lab 3
Move To Front
When searching through a linked list which contains n elements, we have a worst case runtime of O(n) which occurs when what we are looking for either is not in the list, or it is at the end of the list. In general, this cannot be improved upon using a linked list, but in some cases, we might be able to improve things.
Let us suppose that we have more information about how the user is going to access our list; in particular, we know that the user is going to be searching for some values significantly more than others.
Consider the following example:
We have a linked list L which contains the numbers [1..n] looks as follows:
1 => 2 => 3 => ... => n => None
Performing a search on this list for n requires O(n) operations. what if we knew that half of the searches would be for the value n? Then we could speed things up by moving n to the front of the list:
n => 1 => 2 => 3 => ... => n-1 => None
This way we know that half of our searches will only have to examine the first node. Ideally, we would like the elements of our list to be sorted so that those more likely to be searched for occur earlier in the list. (For those with a firm grasp of statistics, this minimizes the expected number of operations search will perform given the probability that each value will be searched for.)
In reality we may not know this distribution, but we can implement our search method to help approximate this ideal ordering of values.
Download movetofront.py and node.py. Your task is to implement the insert and search methods as follows:
insert(self, value) should insert value to the front of the list.
search(self, value) should return False if value is not in the list. If value is in the list, then it should move the node containing value to the front of the list and return True.
Example:
L = MoveToFront()
L.insert(3)
L.insert(2)
L.insert(1)
print L # Should print [1,2,3]
assert L.search(2) # returns True and moves 2 to the front of the list.
print L # Should print [2,1,3]
assert L.search(3) # returns True and moves 3 to the front of the list.
print L # Should print [3,2,1]
assert not L.search(0) # returns False
print L # Shuld print [3,2,1]; the last search should not have altered the ordering.
Note that the more often a value is searched for, the more frequently it is moved to the front of the list.
Implement these two methods, and write some tests. You may wish to consult the linked list implementation from lecture.