Im writing a new terrain engine, My old one used an array like this

CTerData position[10000][10000];

Apart from the fact that I dont like useing an array of this size, I want to make it so I can vary the size of the grid, adding to any direction.

Now I considerd a linked list, but it wouldnt work for me. So my question is, How would you mannage the data in this situation?

The seperate data items need to be ordered in some logical fashion so I can do culling and sorts.