Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 5 / a

Use null to indicate that the requested key is absent:

private def find(name: String, head: Entry): Entry = {
  var cursor = head
  while (cursor != null && cursor.name != name) {
    cursor = cursor.next
  }
  cursor
}

The loop invariant is that the skipped string prefix contains no entry with the requested name and cursor starts the unsearched string suffix of the unchanged bucket. Its remaining length is a loop variant. Short-circuit evaluation prevents accessing a null entry. On exit, either cursor is null and the whole bucket has been ruled out, or its name equals the key. No list links or stored numbers are modified. String comparison here uses value equality; node deletion elsewhere uses reference identity.