I'm also a software engineer, worked on non-gaming embedded systems. Games have the advantage that it is more acceptable to have hiccup now and then, I worked on communications systems where timing was somewhat more important.
Anyway, linked lists are pretty much the classical case of objects that do not fragment memory. Fragmentation occurs when memory alloactions differ in size. Typically this happens with strings. Still, I wouldn't use them here.
The problem is not
storing data for every tile. For that, an extra array is most efficient. The problem is storing properties for a small number of tiles (sparse). One should definitely use a PROP_ID for this that also identifies the property size, and properties should be fixed-size. This speeds up logic. E.g. use the lowest 4 bits for the size,
size_t size = sizeof(PROP_ID) * (aPROP_ID & 0xf)
. (The sizeof is for alignment). This still leaves at least unique 4096 properties, assuming we don't alias PROP_ID's of different sizes (ie when PROP_ID >> 4 is also unique).
After the PROP_ID we can then store the property data.
Only then do we have to deal with the hard stuff, finding properties for a given x/y pair. Basically, there are two solutions: linked lists of properties and concatenated properties. In the first case, each property has a pointer to the next property. In the second, we continue with a new PROP_ID after the propery data of the previous.
We can also use mixed forms, by reserving a special PROP_ID PROP_CONTINUE_IN_NEXT_BLOCK or so. In that case, we concatenate properties in a block until we have space for one last 4-byte property. If we then add it, we allocate a new memory block, add a pointer property in the previous block, and continue in the new block.
This last form is pretty good, because we can then use uniform 32-byte block (hardly any fragmentation) yet still use variable-length properties.
The last point we need to address is the 'first property'. For simplicity, I suggest we initially stick with a [N][N] pointer array. One could perhaps save a few bytes by using an array of arrays, and allocating only those nested arrays for which there are really properties. This saves quite a few bytes near the edges, but it becomes complicated quite soon.