No, you can do this anytime you want to write a value. To initialize the system, fill the array with "available", for example 0xFF's. But, see the "gotcha" at the end here...
To store a new value:
- Begin anywhere you like (because only one valid value is ever stored), seek until you find a non-available (valid data). Remember this position, but no need to store it, you only need it right now!
- Overwrite the old valid data with an "available", e.g. 0x7FFF
- Advance the address by one (and check for wrap around), and store the new value
- Profit.
Notice that you can subdivide the EEPROM and still have this, you just need to define the buffer start and end points - of course the math is easier if you use a power of 2 size and offset.
You're correct about the first time exception, then nothing is stored and it has to stop somewhere rather than repeatedly searching and not finding. The easiest solution for that, is to initialize it with all "available", but also one dummy value.
Subsequently, at any given time, the buffer will contain all "available" markers, except for one valid data value.
For safety, in case corruption happens between overwriting the old value and writing the new one, it might be better to:
- Begin anywhere you like (because only one valid value is ever stored), seek until you find a non-available (valid data). Remember this position, for the overwrite.
- Advance the address by one (and check for wrap around), and store the new value
- Overwrite the old valid data with an "available", e.g. 0x7FFF
- Profit.
If it were interrupted, it would leave behind two data values. But on the next go round, the "extra" advance data would be overwritten. This would preserve the previous data but not the most current one. But it would restore the desired condition of having only one value in the buffer.
As long as you are saving only one data item per buffer, there is never any need to store an EEPROM address in the EEPROM itself.
Also, you are only "blind" at boot time. After that, you can keep a "candidate" address for the data where you can start searching when you want to write. It's foolproof because if it misses, it will just keep looking until it finds data anyway... but in this case, usually you would not have to search the entire EEPROM buffer each time. On boot, the search might succeed at the first location, or the last, depending on where the data was last stored.