Snake game - how to calculate the next apple position

I'm implementing a Snake game in javascript for fun, I have successfully implemented the snake, its movements and the snake-growth thing as it eats an apple.

To calculate the apple position I'm currently following these steps:

1. create a new apple object


2. create random coordinates (X and Y, between game-container boundaries) for the apple


3. check if the coordinates of the apple are equal to one of the snake-blocks coordinates


4. if step #3 is TRUE, recalculate the position of the apple, else draw the apple in the game-container

Unfortunately I found out that this algorithm is very weak.. let's say I have a 10 x 10 game container, the red square is the apple, the green square is my snake head (initial game state)

as the game progresses the snake eats more and more apples, increasing its length and leaving less and less empty cells to place an apple

Now suppose that the snake reaches a length equals to 99 while eating an apple. This means that there's only one square left to place the next apple. My algorithm (this is the worst case obviously) could take forever in order to randomize the correct value, as it discards any randomized position that it's already taken by the snake's head or tail, not caring at all to randomize the new position in a range of "empty cells" only but instead randomizing on the whole 10 x 10 game canvas.

How should I proceed to solve my busillis? Can you give me any advice on a good algorithm that I can use?

Thank you