Hi Stuart

There are lots of solutions to this and I am sure you will get several here at the UT. I would

1) Create an index key on DELETED().
2) When I want to add a new record I would first try to see if a deleted record exists by setting the files index to the deleted tag and using SEEK(.T.). (You would need to SET DELETED OFF for this so that deleted records can be found. You can SET DELETED ON to hide deleted records again but only after step 3).
3) If a record is found then use RECALL to undelete it and update the field values.
4) If no deleted record found then I would create a new record with INSERT INTO or APPEND ... whichever is appropiate.
5) To employ FIFO/LIFO you would set the file to the Deleted index tag and use the Asecnding or Descending options as the case may be.

Hope this gets you started.