SortedTroves: Linked List Sorted by NICR

Key takeaway: SortedTroves maintains every active Trove in a doubly-linked list ordered by Nominal Individual Collateral Ratio — descending, so the head holds the highest NICR and the tail holds the lowest. Liquidations iterate from the tail (riskiest first). Redemptions iterate from the tail (cheapest collateral first). Storage is mapping(address => Node) with prev and next addresses; head and tail are stored separately. Insertion is O(1) given a correct position hint, O(n) walking from the head. The protocol uses off-chain hint computation in production for gas; the academy walks from head — equivalent semantics, no off-chain helper required.

What You Are Building

A custom doubly-linked-list contract that holds every active Trove address sorted by NICR. Why a linked list and not a sorted array? Because Solidity has no native sorted-set data structure, and arrays would require O(n) shifts on every insert. The linked list gives O(1) insert/remove/reinsert given a position hint, and O(n) traversal — which is fine because liquidations and redemptions only touch a bounded number of Troves per transaction (typically 10-100).

The list is sorted by Nominal ICR (coll * 1e20 / debt), not regular ICR. Nominal means no oracle price — just the coll-to-debt ratio. This is critical: if the list were sorted by price-dependent ICR, every oracle update would change the order, and we'd need to re-sort. NICR is stable across price moves — only the threshold for liquidation (coll * price / debt < MCR) changes, not the relative ordering between Troves.