Data structure for a sparse matrix where elements are randomly distributed

I couldn't think of anything else开发者_如何学运维 except a linked list.. Any better idea?

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)).

Quatree matrices (the code used in the paper is there) have reasonably good insertion and access complexities, and reasonably good performance. There are specific algorithms for them (mostly in form of research papers). However they are not really widespread. But they do deserve more love. If you intend to solve systems, a decomposition well suited to quadtree matrices is explained there.

If your matrix will be constructed at once, and you don't need to add/remove elements after it is constructed, then Compressed Row Storage (or compressed column storage) is widespread and efficient, and there are libraries and specific algorithms for dealing with them.

After all, you did not tell us what you want to do with your matrices.

For every non-zero element you need to store its coordinates (row/column) and its value. There is a variety of ways to do that.

Wikipedia has an overview of a bunch of approaches: http://en.wikipedia.org/wiki/Sparse_matrix#Storing_a_sparse_matrix

It is impossible to say what's best for your application without knowing more about the sizes and density of your matrices, memory constraints, expected access patterns and so on.