The orthogonal linked-list is a popular structure for representing sparse matrices. The OLL is essentially a two-dimensional linked list. Each node has two forward pointers: one to the next node in its row, and another to the next node in its column.
There's a great visualization of what this looks like here: http://ultra.pr.erau.edu/~jaffem/classes/cs315/cs315_homework/homework/sparse.htm
Has anyone built such a thing in Rust?
Linked lists are of course a favored topic of Rust challenges (and complaints). The OLL includes all of these pain points, and a few more.
- Each node generally has two incoming pointers, so shared-ownership structures such as
Rcare likely necessary.
- Facilitating common operations (row swap, column swap, value update) highly incentivizes interior mutability, e.g, via RefCell.
- Data in the row and column-header vectors will frequently have (and update) references to their other elements. E.g. rows will have a reference to rows, and often replace it with a reference to rows.
What would the community advice about implementing this? (Or about an existing implementation.)