11.4 S o r t e d L i s t | 545Initial state of listThe state of the list after adding the highlighted item to the
initial list in the appropriate position to keep the list sortedGomezGomez1 item0 items2 itemsApplebeeGomezGomezZiggleGomezNortonApplebeeGomezNortonGomezJonesNortonGomezNortonZiggleFigure 11.6 Inserting Items into a List So That Ordering Is Preserved
Responsibility Algorithms for Class SortedList
Let’s look first at insert. Figure 11.6 illustrates how it should work.
The first item inserted into the list can go into the first position. Because there is only
one item, the list is sorted. If a second item being inserted is less than the first item, the first
item must be moved into the second position and the new item put into the first position.
If the second item is larger, it goes into the second position. If we add a third item that is
smaller than the first item, the other two items shift down by one and the third item goes
into the first position. If the third item is greater than the first item but less than the second,
the second shifts down and the third item goes into the second position. If the third item is
greater than the second item, it goes into the third position.
To generalize, we start at the beginning of the list and scan until we find an item
greater than the one we are inserting. We shift that item and the rest of the items in the
list down by one position to make room for the new item. The new item goes in the list at
that point.