Java data structure for matrix?

Question

What is the best data structure I can use for my matrix that will contain short variables but most of elements are empty..

I could simply use n by b array for the matrix but the problem is that I don't want to waste the memory because only a few elements are in the matrix..

I was going to use a linked list or a hash table but not sure which one would be the best data structure and how to implemente this..

this could help for sparse matrices in java http://stackoverflow.com/questions/390181/sparse-matrices-arrays-in-java if you are going to roll your own, i think the choice of data structure would depend on what kind of operations youll be doing — jon_darkstar, Mar 24 '11 at 06:23

score 5 · Accepted Answer · answered Mar 24 '11 at 06:28

I would implement a Sparse Matrix. Use a HashMap with the row index as keys, and then either a HashMap or TreeMap for the actual elements (with the column index as key). If you are storing primitive types, I would suggest having a look at the Trove Java Collections Framework. It is optimized for use with primitive types. I would suggest using it anyway, as the keys could all be primitive.

score 1 · Answer 2 · answered Apr 09 '12 at 14:07

1

There are also multiple Table implementations from Google Guava libraries

answered Apr 09 '12 at 14:07

Andrejs

26,885
12
107
96

score 0 · Answer 3 · answered Mar 24 '11 at 06:23

0

When the matrix is sparse, its better to use LinkedList. LinkedList will be better than other options in terms of space(provided the matrix is sparse).

But note that LinkedList has O(n) time for access.

answered Mar 24 '11 at 06:23

Suraj Chandran

24,433
12
63
94

Java data structure for matrix?

3 Answers3