How to recover a deleted/replaced HFS+ partition from external drive?

[I'm answering for anybody ending up here, as the original OP most probably is no more interested. I still refer to his problem description.]

I tried using Testdisk 6.13 (latest stable release) and it worked like a breeze for both NTFS and HFS+. I had the luxury of an empty HFS+ partition, so I just removed it and recovered it using Testdisk - it was rather fast.

I followed the following tutorials:

• http://www.dedoimedo.com/computers/linux-data-recovery.html
• http://www.cgsecurity.org/wiki/TestDisk_Step_By_Step

If you indeed just removed one partition, it should be fast. Otherwise, it might take more time, but probably waiting is the most sensible option. But if you're really impatient (as I am) and you know very well what you're doing, you might want to read on.

A (dangerous) tip to speedup Testdisk from my own experience

If the partition entry is just removed, Testdisk will look for the start of the partition in sensible positions (by default, at the start of every cylinder, since partitions should usually be cylinder-aligned), ignoring the existing partition table. Once it thinks it found a partition and you confirm its guess, it will skip searching inside the partition.

If there is a lot of free space (without a filesystem) before the partition, this might be very slow. So I could speed up search a lot by creating a filesystem in an empty partition before the missing one, so that Testdisk would skip that space. However I knew perfectly where to create this filesystem, especially because it did not border with the lost partition. Otherwise, creating such a filesystem can easily destroy the wrong data - hence only attempt this if you know very well what you're doing.