Yep, probably the thing about having free space in the middle isn't right, but there's still a problem. How to prevent two different kinds of data from overwritting each other as they grow?

Yep, the idea you proposed is good. AFAIK it's not what they used in hard disks, as one sector = one file.