Question

Which is the best data structure to represent a sparse matrix?

• A. Linear array
• B. Linked list
• C. Binary tree
• D. Graph

Hint:

You want to store only the non zero entries. Which structure grows with the count of non zeros, not the full grid?

Answer 1

The Correct Option is B

Different angle, count the storage:

Let a sparse matrix have $k$ non zero elements out of $m \times n$ total, with $k \ll m n$.

A linear array must reserve all cells:
\[ \text{cost} = m \times n \]
which is huge and mostly zeros.

A linked list keeps only useful nodes, one per non zero value with its row and column:
\[ \text{cost} \propto k \]
which is tiny when the matrix is sparse.

Trees and graphs add ordering or edge overhead that this simple triple list does not need. The list gives the smallest, cleanest representation.
\[\boxed{\text{Linked list (option B)}}\]