Use the move-to-front heuristic. Replace only 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. 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.
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
} Articles by others on the same topic
There are currently no matching articles.