Representing an sparse matrix in Java using linked lists

Question

I'm making a little program to make a representation of sparse matrixes (a matrix with a lot of elements equal to zero). Represented like this page 108 (I think watching at the figure is enough to understand it) it is using linked lists.

[Don't read this paragraph if you understand the figure]
It must store only elements different of zero, save the row and the column of the element, and link them as follows. First element of the matrix must have the dimensions of it; it is linked to a node that represents the first row that has an element different of zero and that element is linked to two nodes: the element of the matrix itself (links at the right) and the next row that has an element different of zero. That way, the entire matrix is constructed.

Ok I'm having problems thinking about the variables of each class. I have two: Node and Matrix.

public class Node {
    int row;
    int column;
    double value;
    Nodo columnLink;
    Nodo rowLink;
    Nodo nextRowLink;
}

public class Matrix{
    Nodo head;
    Nodo first;
    Nodo last;
}

Is it the best way to go? I mean, when it is a head node it doesn't store anything in value and when it is a non zero element, it doesn't store anything in nextRowLink. I'm asking about the memory use since the purpose of sparce matrix are to not use unnesessary space in memory. What implies nextRowLink = null;?, value is a native variable so, it takes 64 bits even if it is value = 0 or Double.NaN;.

Is it a better way than the one I'm thinking on?

Answer 1

I'd do it like this: a linked list of linked lists

class SparseMatrix {
    ColumnNode head;
    int dimx, dimy;
    // other members
}

class ColumnNode {
    int colNum;
    RowNode head;
    ColumnNode next;
}

class RowNode {
    int rowNum;
    double value;
    RowNode next;
}

which has slightly "slimmer" nodes, is easier to get right with the help of the type system, and allows you to skip the unnecessary "head" nodes by using the head pointers.

If you know each row (column) contains at least one value, switch to an array of column (row) lists.