tl;dr:
We’ll (almost certainly) never know
There is not a single mention, much less explanation, in anything canon in the Potterverse as to where any of the Horcruxes were before they were where they were found in the books. Given how Rowlingmaths works, it’s likely J.K. Rowling herself never even considered it.
It seems likely that it was probably in a previous hiding place somewhere, though.
Long (very long) version:
We’ll probably never know, but here’s a lot of at least reasonably relevant theorising about how the locations of the Horcruxes may hang together.
I have very little canon evidence to back any of this up with, because there simply is nothing relevant in canon that I’m aware of. But it’s way too long to fit in a comment, so it’ll have to be an answer, albeit a highly speculative one. There is not, to my knowledge, a single word in all of canon on the whereabouts of any of the Horcruxes between their Horcrucifixion and their location when they are found in the books.
For ease of memory, these are the Horcruxes in the order they were made, with locations discovered (excluding Nagini who was Horcrucified much later):
- The diary (Sept 1943) – in Lucius Malfoy’s possession from ? until 1992
- The ring (late 1943) – in the Gaunt house from ? until 1996
- The cup (1945–6) – in the Lestrange vault from ? until 1998
- The locket (1945–6) – in the cave from 1979 till 1979
- The diadem (~1956) – in the Room of Requirement from ~1956 until 1998
Two Horcruxes are already accounted for, time-wise: the locket (see the timeline in the question here) and the diadem, albeit tentatively. It is commonly accepted that Voldemort hid the diadem in the Room of Requirement when he came to Hogwarts on the pretext of wanting to teach there, which meeting took place ten years after he killed Hepzibah Smith, around 1956.
The dates of Voldemort’s hiding of the other three Horcruxes are unknown, but at least two of them must have been hidden later than the diadem.
The diary, given to Lucius Malfoy, and the cup, kept in the Lestrange vault, must by necessity both have been placed there after Voldemort made Lucius and the Lestranges’ acquaintance. Malfoy was born in 1954 (according to the Wikia), and both Bellatrix Lestrange and her husband Rodolphus were born some time around that too (1951 and “before 1964”, respectively, according to the Wikia). They would thus have graduated Hogwarts in the late 1960s and early 1970s, approximately, and could not have known Voldemort (who was born in 1926 and graduated Hogwarts in 1945) at school. They likely joined the Death Eaters no sooner than Voldemort’s initial rise to power in the 1970s, a few years after leaving Hogwarts.
We know that the name ‘Voldemort’ and the term ‘Death Eater’ were both coined while Riddle was still at Hogwarts, and it seems a fair presumption that some of his supporters from back then were still amongst Death Eater ranks in the 1970s, old and trusted devotees. Despite this, Voldemort chose to entrust his Horcruxes to two much younger and more recent recruitments to the club. Voldemort is not the kind to trust easily, especially something so important as the safe keeping of a Horcrux, so I think we have to assume that Lucius and the Lestranges (well, mainly Bellatrix I’d say—Rodolphus doesn’t seem to have been considered very much) must have been active Death Eaters for a good while to earn his trust. This puts us suspiciously close to the end of the 1970s, the time when the locket was hidden in the cave.
The ring, unfortunately, must remain a mystery. There is absolutely nothing whatsoever to tell us whether Voldemort hid it as soon as he’d Horcrucified it, at some point later in time prior to his rise to power (like around the time when he hid the diadem), or at the same time as the diary, the locket, and the cup. The first is perhaps rather unlikely, since there were still Gaunts living in the house when he took the ring and made it a Horcrux; but the other two are equally likely.
This paints rather a discordant picture: apparently Voldemort thought to hide the diadem (and possibly the ring) as early as 1956, but he didn’t think to hide the diary, the cup, and the locket (and possibly the ring) until he was pretty much at the height of his power in the late 1970s.
The most logical scenario I can envision to explain this is that he hid all his Horcruxes from the start, but gradually thought of/discovered better hiding places for them. Where they were found was simply the latest of his hiding places. After all, Voldemort may be arrogant, but he’s not daft enough not to realise for 25 years that encasing parts of your soul in Horcruxes is a bit useless if you’re just going to keep the Horcruxes in your dressing room drawer.
He likely hid the ring somewhere unknown at first, then moved it to the Gaunt house when he learnt that Marvolo and Morfin had both died. He hid the diadem at Hogwarts right after he made it in 1956. He hid the locket somewhere unknown after making it, but decided to move it to the cave in 1979. He likely had similar, unknown hiding places for the cup and the diary, but for some reason decided to move them as well later on.
The diary and the cup are the really interesting ones here, I think. The fact that he trusted anyone but himself (even his closest, most valued Death Eaters) with something so important as Horcruxes is quite out of character for Voldemort, and to me it suggests haste, that Voldemort was in a hurry when he gave them to Lucius and Bellatrix.
If we go out on a limb and do a bit of conjecturing, it seems likely that the previous hiding places of these two Horcruxes had somehow been compromised or Voldemort no longer considered them safe. Lucius and Bellatrix’ guardianship could then be meant as only temporary safe keeping until he could set up a more permanent and safer hiding place. Possibly a similar period of Gringotts safe keeping1 had taken place for the locket as well in 1979.
If we accept this, we are almost forced to accept that the diary and the cup were given to Lucius and Bellatrix in 1981, shortly before Voldemort’s failed attempt to kill Harry. Voldemort simply didn’t have time to put them in a new hiding place before he was sorta-kinda-killed. And Lucius and Bellatrix kept the Horcruxes since they had no reason not to.2
All of this still doesn’t answer the actual question as asked in a very satisfactory manner, of course. It shows that there is some inconsistency both in the timeframe of Voldemort creating and hiding Horcruxes, and in the degree to which and manner in which he hid the different Horcruxes. Hopefully, it also gives a way that these inconsistencies can be at least mainly reconciled.
But the most specific thing we can say is that the locket was likely in a previous, unknown hiding place before it was placed in the cave in 1979, but that we have no idea where that hiding place was.
If you’ve read this far, congratulations/commiserations. Have a cookie and a well-deserved rest.
1 I’m assuming here that Lucius was originally told to keep the diary in his Gringotts vault as well, and only dared to take it out to use it much later, when he was more or less certain Voldemort was gone.
2 The major problem with this theory is of course that Voldemort didn’t bother finding a new hiding place for the cup after Bellatrix was freed from Azkaban in 1996. But honestly, there is so much out-of-character inconsistency here that I’m willing to just accept that perhaps he deemed Gringotts to be sufficiently safe, at least for the time being.
