Actually why are you checking if recordNo is null? recordNo is a primitive. It's better to check if it's <=0 or greater than your available total record number. Once such conditions passed then you check if record is already deleted.
So it's not necessary to call isDeleted(recNo) twice.
First of all I would never check seperately if the record is null. That's a check which should definitely be in the isDeleted-method. I guess the isDeleted-method checks the deleted flag to see if it's a valid record or not. I consider this bad design, because the deleted flag is part of the data structure representing a record in the database file, but the deleted flag says something about the state of the record, so it should not be part of the data structure itself. So in your map the value is null (a deleted record) or not null (a valid record). It can't be any simpler than that!
Secondly about the main question: would it not be sufficient to check for a valid record after the locked record is unlocked instead of checking once before and once after? I don't think there are huge benefits when checking twice (except saving a few CPU cycles).
In terms of the deadlock, my other concern is : is the unlock method notifying the waiting threads?
Make sure the waiting threads are waiting for the same lockedRecord object.
For example, one thread does this:
This is a scenario:
1. Thread 1 lock record 1
2. Thread 2 tries to lock record 1, but it waits for it.
3. Thread 1 marks the record as deleted in the database or memory.
3. Thread 1 unlock record 1 , check if record no has been reserved from the memory. If not , throw record not found exception.
4. Thread 1 notifyAll waiting threads, thread 2.
5. Thread 2 wakes up,it finds out the record is not locked anymore. It moves on to the delete method. But it finds out that the record is deleted in the delete method, throws the exception, which is caught.
6. When the exception is caught, you can put the unlock method in the finally method.