Inserting Items in a Sorted List

When inserting an item into a sorted list we have as a precondition  that the list is already sorted. Furthermore, once the item is inserted, we have the postcondition  that the list must still be sorted. Therefore, all the items initially in the list that are larger than the item to be inserted need to be moved to the right by one position as shown in Figure .

  
Figure: Inserting an item into a sorted list implemented as an array.

Program  defines the insert method for the SortedListAsArray class. This method takes as its argument the object to be inserted in the list. Recall that the insert method provided by the ListAsLinkedList class simply adds items at the end of the array. While this is both efficient and easy to implement, it is not suitable for the SortedListAsArray class since the items in the array must be end up in order.

  
Program: SortedListAsArray class insert method.

The insert method given in Program  first checks that there is still room in the array for one more item. Then, to insert the item into the list, all the items in the list that are larger than the one to be inserted are moved to the right. This is accomplished by the loop on lines 9-14. Finally, the item to be inserted is recorded in the appropriate array position on line 15.

In the worst case, the item to be inserted is smaller than all the items already in the sorted list. In this case, all items must be moved one position to the right. Therefore, the running time of the insert method is O(n).

Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.