You're looking for a sparse array. You don't need a linked list (though that is one option). If you normally have a 3-d array of Foo objects, like so:
Code:
Foo foo_array[100][200][300]
You have 6 million Foo objects. If most of them are 0/null, you can simply store the indices of each non-null element, along with the element itself, in an array. For example:
Code:
struct sparse_element {
int x; // first dimension
int y; // second dimension
int z; // third dimension
Foo f; // the foo object that would be at foo_array[x][y][z]
};
Then, you have an array of sparse_elements:
Code:
struct sparse_element sparse_array[500];
That's much smaller, but the savings in space are often offset by extra computation time to find/access members*. Just pick an appropriate number of elements**. Also, you will probably want to malloc this array in your code.
* There are other ways to speed up access to these sparse elements, perhaps keeping the array sorted for a binary search, or by using a balanced binary tree to store them instead of a fixed array, so looking for the Foo object that would be at (x,y,z) = (75,42,19). Not as quick as simply indexing an array, but better than a linear search.
** As for the appropriate number of elements, that depends on your application, since there is a little extra overhead. You may find that this method is only effective if your original array was less than 10% full, or maybe 25%, 50% or even 75%.