Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 4 / f / 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.