3.3.1 Insertion

Suppose you wish to insert a new record for CHRYSLER. It is always a good idea to sketch an image like Figure 3.6(a) to show both the situation at the outset and the situation desired after the task is carried out. Since only the head of the list, stocks, is assumed known, normally each record of the list must be accessed in turn, starting from the first, in order to determine where to make the insertion. For now, assume there is a given pointer predecessor that points to the record after which the new record is to be inserted. In the example, this is the second record. The value of its link field must be copied into the link field of the new record, so the new record's link field points to the successor of the predecessor record. The link field of the predecessor record must end up pointing to the new record, so the value of newpointer must be copied into the predecessor's link field. The code to accomplish this may be written as

setlink(newpointer,next(predecessor));

setlink(predecessor,newpointer);

where setlink is a function that copies the value of its second parameter into the link field of the record pointed to by its first parameter, and next is a function whose value is a copy of the link field value of the record pointed to by its parameter. Why is it incorrect to interchange these two statements?

Notice that no assumptions have been made about the implementation of the list. The code is thus independent of how the list is implemented. Of course, setlink can be written only when the implementation is known, and it will depend on the details. However, this code will not. The list is thus a data abstraction with insertion as one of its operations; deletion is another.

Figure 3.6 Insertion of a New Record (a) in the Interior of a List and (b) at the Front of a List