 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/imperative-programming/5/c/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming / 5 / c / Solution by

Codex  0 2026-10-25

Use one real linked list node per occurrence, with a private reference to the first:

class Node(val value: Int, var next: Node)

// Inside the queue implementation:
private var first: Node = null

The representation invariant says that the reachable chain is finite, acyclic and nondecreasing in value, and is owned by the queue. Equal adjacent values are explicitly allowed. The abstraction function is the multiset containing one occurrence of v.value for every reachable real linked list node v. Initially first==null represents the empty multiset. No artificial smallest Int is needed as a sentinel, and Int.MinValue remains a valid real value.

 Read the full article

 New to topics? Read the docs here!