Building a sparse matrix in Java w/o using hashtables?

In my project, I'm trying to build an adjacency matrix for a graph, and for space and time considerations we are supposed to use a sparse matrix, which, from my understanding, is most easily done with a hashmap. Unfortunately, we also had to implement a adjacency list, which I implemented with said hashmap, and s开发者_运维技巧ince our adjacency matrix has to be structurally different I can't use a hashmap for the matrix. Is there any other way of implementing one?

For an n-dimensional matrix, you can use a variant of a Binary Tree. When inserting etc, what you do is cycle through the dimensions until you find a leaf.

So for a simple two-dimensional dataset, say (2, 5), (10, 1), (5, 6), (3, 4) inserted in that order, you would get

 (2, 5)
    \
   (10, 1)
       \
      (5, 6)
        /
    (3, 4)

(2, 5) gets inserted at root.

(10, 1) goes right because 10 > 2.

(5, 6) goes right of (2, 5) because 5 > 2. Then it goes right of (10, 1) because 6 > 1.

(3, 4) goes right 3 > 2. Then right 4 > 1. Then left 3 < 5.

The wikipedia page on Sparse Matrices lists 6 alternatives:

• Dictionary of keys (DOK).
• List of lists (LIL)
• Coordinate list (COO)
• Yale format
• Compressed sparse row (CSR or CRS)
• Compressed sparse column (CSC or CCS)

Another alternative is an Adjacency List.

Finally, you should also consider representing the adjacency matrix as a bitmap, mapping each matrix cell to a specific bit. (A typical JVM represents a boolean[] as an array of machine bytes with one boolean per byte.) When you consider the space overheads of Java hash tables and lists, an adjacency matrix needs to be rather large ... and sparse ... before the more complicated "sparse" data structures give you a space saving.

You could use a list of lists or a coordinate list.

Try a List<SparseIntArray>, using ArrayList as List implementation, or a plain array SparseIntArray[] if you know the size.

SparseIntArray is a pretty small isolated class from google android.

Here is how I leverage it to represent Sparse matrices with common operations. It's very memory efficient.