Hacking the $O(n)$ Find

Consider the following implementation of find:

private Node<T> find(T t) {
  for (Node<T> n = head; n != null; n = n.next) {
    if (n.data.equals(t)) {
      return n;
    }
  }
  return null;
}

Exercise Update the implementation of find to employ the "move-to-front heuristic" as it is described in the "Dictionary of Algorithms and Data Structures".

Solution

Assuming there are helper methods remove and prepend, you can remove the target node and then prepend it to the list.