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

Starting at last.next, visit each node once and stop when the traversal would return to its start. This helper is private so that callers do not receive writable nodes from the representation.

private def find(name: String): Node = {
  if (last == null) return null
  val first = last.next
  var p = first
  do {
    if (p.name == name) return p
    p = p.next
  } while (p ne first)
  null
}

Null means no entry has that name. The test p ne first compares object identity, not the equality of name or number fields. At each iteration all previously visited nodes failed the name test. The finite simple cycle guarantees that either a match is found or the traversal returns to first after exactly one turn. A singleton cycle is inspected exactly once. Stopping at null instead would fail to terminate on this representation.