# Sparse Matrix and its representations | Set 1 (Using Arrays and Linked Lists)

A matrix is a two-dimensional data object made of m rows and n columns, therefore having total m x n values. If most of the elements of the matrix have 0 value, then it is called a sparse matrix.

Why to use Sparse Matrix instead of simple matrix ?

• Storage: There are lesser non-zero elements than zeros and thus lesser memory can be used to store only those elements.
• Computing time: Computing time can be saved by logically designing a data structure traversing only non-zero elements..

Example:

```0 0 3 0 4
0 0 5 7 0
0 0 0 0 0
0 2 6 0 0
```

Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in the matrix are of no use in most of the cases. So, instead of storing zeroes with non-zero elements, we only store non-zero elements. This means storing non-zero elements with triples- (Row, Column, value).

Sparse Matrix Representations can be done in many ways following are two common representations:

1. Array representation

Method 1: Using Arrays

2D array is used to represent a sparse matrix in which there are three rows named as

• Row: Index of row, where non-zero element is located
• Column: Index of column, where non-zero element is located
• Value: Value of the non zero element located at index – (row,column)

`// C program for Sparse Matrix Representation`
`// using Linked Lists`
`#include<stdio.h>`
`int` `main()`
`{`
`    ``// Assume 4x5 sparse matrix`
`    ``int` `sparseMatrix[4][5] =`
`    ``{`
`        ``{0 , 0 , 3 , 0 , 4 },`
`        ``{0 , 0 , 5 , 7 , 0 },`
`        ``{0 , 0 , 0 , 0 , 0 },`
`        ``{0 , 2 , 6 , 0 , 0 }`
`    ``};`
`    ``int` `size = 0;`
`    ``for` `(``int` `i = 0; i < 4; i++)`
`        ``for` `(``int` `j = 0; j < 5; j++)`
`            ``if` `(sparseMatrix[i][j] != 0)`
`                ``size++;`
`    ``// number of columns in compactMatrix (size) must be`
`    ``// equal to number of non - zero elements in`
`    ``// sparseMatrix`
`    ``int` `compactMatrix[3][size];`
`    ``// Making of new matrix`
`    ``int` `k`
`    ``for` `(i = 0; i < 4; i++)`
`        ``for` `(j = 0; j < 5; j++)`
`            ``if` `(sparseMatrix[i][j] != 0)`
`            ``{`
`                ``compactMatrix[0][k] = i;`
`                ``compactMatrix[1][k] = j;`
`                ``compactMatrix[2][k] = sparseMatrix[i][j];`
`                ``k++;`
`            ``}`
`    ``for` `(i=0; i<3; i++)`
`    ``{`
`        ``for` `(j=0; j<size; j++)`
`            ``printf``(``"%d "``, compactMatrix[i][j]);`
`        ``printf``(``"\n"``);`
`    ``}`
`    ``return` `0;`
`}`

Output:

```0 0 1 1 3 3
2 4 2 3 1 2
3 4 5 7 2 6
```

In linked list, each node has four fields. These four fields are defined as:

• Row: Index of row, where non-zero element is located
• Column: Index of column, where non-zero element is located
• Value: Value of the non zero element located at index – (row,column)
• Next node: Address of the next node

`// C program for Sparse Matrix Representation`
`// using Linked Lists`
`#include<stdio.h>`
`#include<stdlib.h>`
`// Node to represent sparse matrix`
`struct` `Node`
`{`
`    ``int` `value;`
`    ``int` `row_position;`
`    ``int` `column_postion;`
`    ``struct` `Node *next;`
`};`
`// Function to create new node`
`void` `create_new_node(``struct` `Node** start, ``int` `non_zero_element,`
`                     ``int` `row_index, ``int` `column_index )`
`{`
`    ``struct` `Node *temp, *r;`
`    ``temp = *start;`
`    ``if` `(temp == NULL)`
`    ``{`
`        ``// Create new node dynamically`
`        ``temp = (``struct` `Node *) ``malloc` `(``sizeof``(``struct` `Node));`
`        ``temp->value = non_zero_element;`
`        ``temp->row_position = row_index;`
`        ``temp->column_postion = column_index;`
`        ``temp->next = NULL;`
`        ``*start = temp;`
`    ``}`
`    ``else`
`    ``{`
`        ``while` `(temp->next != NULL)`
`            ``temp = temp->next;`
`        ``// Create new node dynamically`
`        ``r = (``struct` `Node *) ``malloc` `(``sizeof``(``struct` `Node));`
`        ``r->value = non_zero_element;`
`        ``r->row_position = row_index;`
`        ``r->column_postion = column_index;`
`        ``r->next = NULL;`
`        ``temp->next = r;`
`    ``}`
`}`
`// This function prints contents of linked list`
`// starting from start`
`void` `PrintList(``struct` `Node* start)`
`{`
`    ``struct` `Node *temp, *r, *s;`
`    ``temp = r = s = start;`
`    ``printf``(``"row_position: "``);`
`    ``while``(temp != NULL)`
`    ``{`
`        ``printf``(``"%d "``, temp->row_position);`
`        ``temp = temp->next;`
`    ``}`
`    ``printf``(``"\n"``);`
`    ``printf``(``"column_postion: "``);`
`    ``while``(r != NULL)`
`    ``{`
`        ``printf``(``"%d "``, r->column_postion);`
`        ``r = r->next;`
`    ``}`
`    ``printf``(``"\n"``);`
`    ``printf``(``"Value: "``);`
`    ``while``(s != NULL)`
`    ``{`
`        ``printf``(``"%d "``, s->value);`
`        ``s = s->next;`
`    ``}`
`    ``printf``(``"\n"``);`
`}`
`// Driver of the program`
`int` `main()`
`{`
`   ``// Assume 4x5 sparse matrix`
`    ``int` `sparseMatric[4][5] =`
`    ``{`
`        ``{0 , 0 , 3 , 0 , 4 },`
`        ``{0 , 0 , 5 , 7 , 0 },`
`        ``{0 , 0 , 0 , 0 , 0 },`
`        ``{0 , 2 , 6 , 0 , 0 }`
`    ``};`
`    ``/* Start with the empty list */`
`    ``struct` `Node* start = NULL;`
`    ``for` `(``int` `i = 0; i < 4; i++)`
`        ``for` `(``int` `j = 0; j < 5; j++)`
`            ``// Pass only those values which are non - zero`
`            ``if` `(sparseMatric[i][j] != 0)`
`                ``create_new_node(&start, sparseMatric[i][j], i, j);`
`    ``PrintList(start);`
`    ``return` `0;`
`}`

Output:

```row_position: 0 0 1 1 3 3
column_postion: 2 4 2 3 1 2
Value: 3 4 5 7 2 6

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org```