3.2.1 Insertion and Deletion of Records in Lists

Consider the effects of inserting and deleting on a conceptual list. The effect of inserting a new record is shown in Figure 3.4. The new record is inserted between the records labeled predecessor and successor. This requires changing predecessor's link to point to the new record, and setting the new record's link to point to successor.

Figure 3.4 Insertion of a New Record in a Conceptual List

Figure 3.5 Deletion of a Record from a Conceptual List

The deletion of a record from a list is shown in Figure 3.5. The record labeled removed is deleted from the list by arranging predecessor's link to point to successor. The rearrangement of links for insertion or deletion is independent of where in the list the operation occurs. Each operation can be performed in constant time. Lists, unlike arrays, readily accommodate change; they exhibit no growing pains (or contraction pains).