Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 4 / d / Solution

Check that at least one real node exists, then compose the two helpers:

def deleteMin(): Int = {
  require(bagHeader.next != null, "bag is empty")
  val smallest = findMin(bagHeader.next)
  val answer = smallest.datum
  delete(smallest)
  answer
}

The precondition check makes findMin applicable. Its result belongs to the real-node sequence, satisfying delete's precondition. Consequently one minimum value is returned and exactly one occurrence is removed; duplicates remain as distinct nodes. Saving the datum before deletion also separates the return value from subsequent link mutation. Two linear traversals still give $O(m)$ time for a multiset containing $m$ nodes, with constant auxiliary space.