Search code examples
csparse-matrix

C, question for data structure for a sparse 2d matrix

I was wondering what data structure I could use for a sparse 2d matrix if I know the element will be a short type. I was going to use a linked list but the element type (short) make any difference? What if the elements are going to be a integer type instead of short type then how would it change the data structure?

Solution

  • Vector of 

    struct {
  int x;
  int y;
  short value;
}

    The value is probably going to end up using 4bytes though (struct members are typically padded to 32bit boundaries) If you are really short of space and the x,y coords are limited you could pack the whole thing into the bits of a 64bit int

    If you are adding and removing points then there might be a case for a list, but typically sparse arrays have a fixed set of points or lookup dominates and it's worth resorting them by X,Y after adding points.

    If you do need to add lots of points AND still want fast access by x,y then a tree might be worth looking at