= Solution
Update an existing node, otherwise append one fresh node while preserving the cycle:
``
def store(name: String, number: String): Unit = {
val p = find(name)
if (p != null) p.number = number
else {
val fresh = new Node(name, number, null)
if (last == null) {
fresh.next = fresh
last = fresh
} else {
fresh.next = last.next
last.next = fresh
last = fresh
}
}
}
``
For an existing name, changing only its number realizes replacement in the abstract <partial function>. On an empty book, the new node points to itself, establishing a singleton cycle. On a nonempty book, its successor becomes the old first node and the old last points to it; advancing `last` leaves the first node unchanged and closes the enlarged cycle. Since a full search established absence, name uniqueness is preserved. Thus the <postcondition> is exactly the old book with this name mapped to the supplied number, and all other entries unchanged. A store takes $O(K)$ <running time> for the name search and $O(1)$ additional pointer work.
Back to article page
