1. Write an algorithm for printing a singly linked list in reverse, using only constant extra space. This instruction implies that you cannot use recursion but you may assume that your algorithm is a list member function. Can such an algorithm be written if the routine is a constant member function?
2. a. Write an array implementation of self-adjusting lists. In a self-adjusting list, all insertions are performed at the front. A self-adjusting list adds a find operation, and when an element is accessed by a find, it is moved to the front of the list without changing the relative order of the other items.
b. Write a linked list implementation of self-adjusting lists.
c. Suppose each element has a ?xed probability, pi, of being accessed. Show that the elements with highest access probability are expected to be close to the front.