Deleted all partitions on a drive by mistake, what are some good free recovery tools?

So I just did something incredibly stupid. I'll save you the story (unless you want it). Basically I deleted the partitions on a hard drive by mistake thinking it was another corrupt drive attached to the system. I haven't written any data to the drive and I haven't created any new partitions, so I'm hoping everything is still there and a tool should make easy work of it.

It was an NTFS formatted drive that had the partitions deleted using Gparted. I then created a new partition table after that and attempted to create a new NTFS partition in its place, but that last part failed. I then rebooted the machine (Ubuntu server running XFCE) and noticed my mistake. Promptly shut down and removed the drive.

So what are some good (hopefully free) recovery tools I could try assuming it's not totally hosed based on above description?

Have a look at testdisk on linux, I haven't used it to recover partitions but I'm pretty sure it has that functionality.

Testdisk is a good choice. I once formatted my entire HDD by accident and was able to recover almost all of my lost data with it.

That's great, even if I can get most of it, I will be happy. I installed testdisk on my linux box thanks to @Dexter_Kane 's suggestion and I'm testing it on another drive to see what it can do and to get the process down just so I don't make any more mistakes on the actual drive.

Edit: Looks like my test worked, so I suppose I will try it on the actual drive.
Edit 2: odd, looks like the test drive is mountable in linux, but Gparted asks if it is GPT or not. Yes or No still reports that it has no partitions. I expected it to fix that completely, maybe just false expectations.