While PhotoRec will recover lost files, what happens when an entire disk partition vanishes? Enter TestDisk.
The ideal situation will be that after you realized you wrongly deleted that partition, that you boot up with a Live CD or Flash Drive. Connect to the Internet, then open Software Manager and search for TestDisk (remember to include the Universe repository in the settings).
When you recover data it is always better to recover it to a different drive, the ideal would be a large external HDD.
For an in depth look at TestDisk check out the HowToGeek tutorial here. At the moment I don't have a test machine and I am sadly not going to risk deleting an important partition on my laptop for this tutorial.
Sorry folks, maybe some day I will revisit this when I have a test machine and an empty external HDD.
Thank you for understanding.