I have Ubuntu and Windows 7 on my PC. My linux partition was accedentaly deleted. So, I'm trying to recover deleted partition with Testdisk, and I'm using Ubuntu Live CD since my Linux partition is deleted. I have found my files with the software, but where should I recover them. Can I recover them on the deleted partition(the unallocated space which was linux previously) without any problem of overwriting and permanent data loss?
No, unfortunately we can't store recovered files on the same partition of a drive. As soon as we start writing on that partition all file-remnants that still reside there will be overwritten with the new data, hence making them irreversibly unrecoverable.
In case there is another partition different to the space we want to recover we may successfully harvest our files to there, but still we can not restore the partition table, as this affects the whole drive's partitioning.
To be on the safe side it is recommended to harvest recovered files on another, possibly external drive.
Yes, it will just restore the partition record. No data from the Windows partition will be lost, the Linux data won't be touched too.
EDIT: After deleting and recovering partitions from an old drive, here's the result (F:, shared, has music in it, restored and G: made by mistake before deleting F:)