“Here follows one of the last notes in the Red Book: We have heard tell that Legolas took Gimli, Glóin’s son with him because of their great friendship, greater than any that has been between Elf and Dwarf. If this is true, then it is strange indeed: that a Dwarf should be willing to leave Middle-earth for any love, or that the Eldar should receive him, or that the Lords of the West should permit it. But it is said that Gimli went also out of desire to see again the beauty of Galadriel; and it may be that she, being mighty among the Eldar, obtained this grace for him. More cannot be said of this matter.” (LOTR, App. A)
Context
While it is not stated who specifically wrote this note, it is known that Frodo wrote the events of the Red Book which concerned the War of the Ring. This would imply that he had written, or at least knew about, the aforementioned note, acknowledging Legolas by name.
It was also further implied that the fact that Legolas’s and Gimli’s ship would sail in the future was known at the time of writing. This speculation might have passed into conversation that was not explicitly stated.
Since Gimli was the first and only dwarf to sail to the Undying Lands, it would be thus, strange indeed. It was anticipated at the time that Legolas will one day go with Gimli due to the significance of their friendship – the greatest of friendships between any Elf and Dwarf – implying that it was written long before the event.
But it was also implied in this writing that Gimli would go also for Galadriel and she would obtain this grace for him. The recalled events leading to their departure would all occur before the breaking of the Fellowship – mainly in Lothlorien.
Movie scene
While there’s a scene in the movies where Frodo seems to have forgotten Legolas name, it is my opinion that it is not very significant, as this does not seem to be evident in his writing.
It is also about their communication, about how an elf communicates compared to other characters.
Elves’ Communication Styles
The High Elves’ had a few main forms of communication: ‘fanar,’ the physical which was adopted by the spirits and other forms of communication in visual forms. They could communicate a desired “vision” direct to another mind.
This would mean they’d be able to communicate their vision to one another – and the mind of the recipient would translate it to words and terms, which resembled what Tolkien calls a ‘fana.’ The strength of this communication depended on the power of the mind. In Quenya, these visions were called indemmar, meaning ‘Mind-Pictures.’ Both Men and Elves used it, though for Men, they experience it best during sleep and dreams, as they could be shaky if experienced while awake.
It is also to be expected that the two would not speak as often as one would expect throughout the series – considering the fellowship splitting, the different tasks they each had to deal with, and meeting for the first time in the Council of Elrond in Rivendell.
Lothlorien + other interactions
They do, however, share more than the one line that is known from the movies. An entire discussion takes place between them in the Great River about perception of time, which starts with Sam:
‘Well, I can remember three nights there for certain, and I seem to remember several more, but I would take my oath it was never a whole month. Anyone would think that time did not count in there!’
‘And perhaps that was the way of it,’ said Frodo. ‘In that land, maybe, we were in a time that has elsewhere long gone by. It was not, I think, until Silverlode bore us back to Anduin that we returned to the time that flows through mortal lands to the Great Sea. And I don’t remember any moon, either new or old, in Caras Galadhon: only stars by night and sun by day.’
Legolas stirred in his boat. ‘Nay, time does not tarry ever,’ he said; ‘but change and growth is not in all things and places alike. For the Elves the world moves, and it moves both very swift and very slow. Swift, because they themselves change little, and all else fleets by: it is a grief to them. Slow, because they do not count the running years, not for themselves. The passing seasons are but ripples ever repeated in the long long stream. Yet beneath the Sun all things must wear to an end at last.’
‘But the wearing is slow in Lórien,’ said Frodo. `The power of the Lady is on it. Rich are the hours, though short they seem, in Caras Galadhon, where Galadriel wields the Elven-ring.’
(FOTR, “The Great River”)
Earlier before they left Lothlorien, Legolas also introduces the company to the voice and Song of Nimrodel.