Hacking the $\Omicron(n)$ Find

  • Understand move-to-front heuristic well enough to implement it.

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 helper methods remove and prepend exist, you can remove the target node and then prepend it to the list.