Figure 3.7 Deletion of a Record (a) from the Interior of a List and (b) from the Front of a List
An alternative that avoids the special case of inserting a new first record assigns a special record, called a header record, to every list as its first record. This record is a dummy record. The dummy is so called because it is not part of the conceptual list of records being created. Used to make processing easier, the dummy record is never deleted, and no record is ever inserted in front of it. Then the special case never occurs, and the original code, requiring no check for the special case, can be used. Actually the header record can be a smart dummy, used to contain important information about the list, such as the number of records. When this alternative is used, the null list can no longer be recognized by a null value in the list head. It is recognized by a null pointer in the link field of the dummy record.
Figure 3.7 Deletion of a Record (a) from the Interior of a List and (b) from the Front of a List