= Solution
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\leq size\leq 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.
Back to article page
