please explain space replacement in memory

[FromU2Me2]

Okay, i lost a camera phone video by accidentally deleting it from internal memory (no sd card in phone yet). I read where people say "stop using your phone"...well it is taking forever for me to find a quick recovery solution for Samsung galaxy note II SGH-1317. I was at work and accidentally downloaded a video and i was wondering how internal memory space replacement works? Does it write over the video i lost a while back first or does it go to other clean spaces and write on that first?