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?

Fred Foo · Accepted Answer · 2011-03-24 22:10:14Z

2

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.

edited Mar 24, 2011 at 22:10

answered Mar 24, 2011 at 22:04

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Roger Over a year ago

The last RowNode must be linked to a ColumnNode, there is a problem since they are different classes, no? look at the figure(books.google.com/…)

Fred Foo Over a year ago

@Roger: you can make both types of list cyclic if you want, just like in the picture: point the last RowNode's next to the first RowNode in its column. That would require empty nodes to support empty rows/columns, though. (I don't see what algorithm would benefit from this setup...)

Ted Hopp · Accepted Answer · 2011-03-24 22:05:57Z

0

You can define a parent class Nodo that contains neither a value field nor a nextRowLink field. Then you can define two subclasses: RowHead that has a nextRowLink and NodoConData that has a value field. Use the first one for the row head and the other for the rest of the nodes on the row.

answered Mar 24, 2011 at 22:05

Ted Hopp

235k48 gold badges413 silver badges533 bronze badges

1 Comment

Roger Over a year ago

The last NodoConData must be linked to a RowHead, they have the same parent class, but, isn't there a problem? How about the later questions? What is the use of memory of nextRowLink = null; and the one with the double object.

Collectives™ on Stack Overflow

Representing an sparse matrix in Java using linked lists

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related