Okay, you understand that the first byte of each record is used to determine if a record is marked as deleted.
You now need to think about what impact that flag will have on the create, delete, read, update, find and other methods in your Data class.
For example the documentation for the create method states that
Creates a record in the database (Possibly reusing a deleted entry)
So for this method you would need to loop through the records in the file until you find a record which is marked for deletion i.e has a value of 0xFF. Then all you have to do is update the information for the record.
You also want to think why a RecordNotFoundException might be thrown.
Jason.