Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming / 8 / a / Solution

Store the current list in a mutable field; insertion and deletion can use its head:

class MSet[T](contents: List[T]) {
  protected var data: List[T] = contents

  def add(x: T): Unit = {
    data = x :: data
  }

  def delete(): T = data match {
    case x :: xs => data = xs; x
    case Nil => throw new NoSuchElementException("MSet.delete")
  }
}

The representation invariant interprets the list by its multiset of occurrences; order is immaterial and duplicates remain distinct occurrences. add increases one multiplicity, while delete returns and removes one occurrence. The field is protected so the minimum-search subclass in part (d) can inspect it. Both successful updates take $O(1)$ list operations. Deleting from an empty bag raises an explicit exception.