Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 3 / c

Keep a head, a tail and a cached length:

private var first: QueueNode = null
private var last: QueueNode = null
private var size = 0

The representation invariant requires $0\le size\le Int.MaxValue$ and a finite acyclic null-terminated linked list of exactly size nodes starting at first. When size == 0, both endpoints are null. Otherwise last is precisely the final reachable node and last.next == null.

The abstraction function maps the chain from first to last to its payload sequence. Initially all pointers are null and the cached size is zero, giving the empty abstract queue. A tail pointer makes append constant-time; the cached size makes the length query constant-time without traversing the chain.