For very large systems, I would suggest that you use some ready-to-use product, since development of such program takes significant time and effort.
In order to store such matrix, you will need to use some scheme like the linked list (or a similar one, so-called "adjacency structure", which is broadly used for storing graphs). Ideally, the matrix storage should be hidden inside the solver, and the elements of the matrix are passed into the solver one-by-one. Good solvers include such function, and the user just needs to call that function, with the row and column indexes and the value of the element itself. When the complete matrix is internally stored, the user calls another function, into which the system right-hand side is passed, and the solution vector is returned upon completion of the solution process.
Below is a reference to one of such solvers, which is capable of solving sparse systems containing millions of equations on just an ordinary PC: