Parts of this answer comes from: How to recover deleted partition table information and I would point @Prash to that question in first instance but nobody saw my previous answer useful so I place it here just in case you may wish to give this a chance.
First of all, stop using the disk immediately. And don't do anything
to it unless you are sure it will result in your disk's partition
recovery, otherwise you may harm your data when attempting to recover
it.
After that, all the testdisk related posts are useful for the specific
case, as you mention. And for your specific case please have a look at
this video by Amzertech in Youtube, which explains exactly what to do
when deleting a partition the way you did.
http://www.youtube.com/watch?v=EncqYP1ijFg
If everything is fine and you have not done anything harmful to your
disk, there are good chances for you to bring the whole partition back
with ease, after which I will suggest you to back up everything,
format the disk again and place the data inside of it, in order to
avoid crossed clusters and these things. Which reminds me that if your
hard disk drive is having crossed clusters or data you may lose a lot
of information.
Give testdisk a chance and please inform if you succeed on it by
commenting on the answers to your question.
You can download a testdisk binary to run it directly from a terminal in a Ubuntu live session or if you wish to go directly to the rescue mode in a terminal (no GUI) you can use the pre-built Hirens Boot which already has a lot of useful tools to recover data, which includes but does not limit only to testdisk.
Just have in mind that testdisk will allow you to bring back your deleted partition and in the other hand you will be able to rescue your deleted data in a per-file basis.
Let us know how do you do with this task and if need further assistante don't hesitate to drop a comment.
Good luck!