= Solution
Use the <move-to-front heuristic>. Replace only `recall` in `LinkedBook` by:
``
def recall(name: String): String = {
require(name != null)
val p = findPrev(name)
require(p.next != null, "Name is not in the book")
val found = p.next
if (p ne header) {
p.next = found.next
found.next = header.next
header.next = found
}
found.number
}
``
The search has the same <loop invariant> and <loop variant> as before. Detach the existing <linked list node> before inserting it immediately after the <dummy header node>. The branch for an already-first <linked list node> avoids linking it to itself. Every real contact still occurs exactly once with the same name/number binding, so the <representation invariant> and <abstraction function> are preserved at return. \b[No new <linked list node> is allocated, and an immediate repeated recall needs one name comparison.] The present recall still pays its original search cost; the gain is for later repeated access.
Back to article page
