In the beginning, the head of the avail list is -1 (empty). When a record is deleted, it is marked by an asterisk, a bar, and a link (the offset of the next deleted record) and is added to the list. After some operations applied to the book information file, its contents may become the following:
243 560
81 12 File Structures: An Object-Oriented Approach with C++ |0201874016|94.80|360|
52 105 *|-1 g WML & WMLScript |1565929470|17.48|12|
62 169 XML in a Nutshell, 2nd Edition|0596002920|39.95|39|
39 243 *|465 nd XSLT |0596001436|26.37|890|
84 294 WAP Servlets: Developing Dynamic Web Content With Java and WML|047139307|32.99|4|
63 390 WAP Development with WML and WMLScript|0672319462|18.99|56|
83 465 *|105 in Security and Payment Methods for Mobile Commerce|1591403456|89.95|182|
79 560 M Commerce: Technologies, Services, and Business Models |0471135852|23.09|5|
where the head of the avail list is an offset 243 and there are three deleted records. The avail list is
head = 243 —> 465 —> 105 —> -1 = end
A record is later requested to be added to the book file. Instead of appending the record at the end of file, a record in the avail list is reclaimed to save space.
They are many ways, placement strategies, to select a record to be replaced.
They will be discussed later.
A simple placement method, first-fit, is explained here.
It sequentially searches the avail list and selects the first available record slot large enough to hold the new record. For example, the previous file becomes the following after the addition:
243 560
81 12 File Structures: An Object-Oriented Approach with C++ |0201874016|94.80|360|
52 105 *|-1 g WML & WMLScript |1565929470|17.48|12|
62 169 XML in a Nutshell, 2nd Edition|0596002920|39.95|39|
39 243 *|105 nd XSLT |0596001436|26.37|890|
84 294 WAP Servlets: Developing Dynamic Web Content With Java and WML|047139307|32.99|4|
63 390 WAP Development with WML and WMLScript|0672319462|18.99|56|
83 465 Dynamic WAP Application Development |1930110081|34.59|18|
79 560 M Commerce: Technologies, Services, and Business Models |0471135852|23.09|5|
where the newly added record is appended with spaces until its length reaches 83.
If no deleted records are large enough to store the incoming record, it is then appended at the end of the file.