Data structure for a sparse matrix where elements are randomly distributed

Question

I couldn't think of anything else except a linked list.. Any better idea?

Answer 1

If you're storing elements in a matrix, you may want to consider using a hash table from coordinates to their contents. This lets you look up the contents of any matrix location much more quickly than if they were stored in a linked list (namely, O(1) rather than O(n)).