Whats the best data structure to use for implementing a sparse matrix

This is an interview question:

A sparse matrix is a matrix that is mostly 0s, whats the best data structure to use to implement this? A dense matrix is a matrix with mostly non-zeros, which data structure is the best to use?

I answered linked list for sparse matrix and the interviewer wasn't impressed.