Where does the extra space go on a replaced partitioned disk?

The data will all be place on the drive on a "first come, first served" basis. If you were to use a tool to defrag and optimize it (and you should actually do this), you'd find all the data stacked up and the rest of the drive clear. The way of storing data is actually why you should defragment and optimize the files and volumes occasionally. Lets say you trash a piece of data, that leave a gap in the continuous data. Next your write a larger piece of data. The new data will be fragmented as the old gap will be filled first and the rest would be stored on the first available area. So three gaps and the new stuff could already have four segments. This forces the drive to work harder and it takes longer to locate all the pieces when opening something. After a couple of years you get a very noticeable speed decrease and you think your computer's just getting old.